공부공간

BOJ - 14500 ) 테트로미노 본문

알고리즘/구현,시뮬

BOJ - 14500 ) 테트로미노

개발자가될수있을까? 2020. 8. 27. 22:56

 

https://www.acmicpc.net/problem/14500

 

14500번: 테트로미노

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변�

www.acmicpc.net

 

 

 

모든점에서 나타날수있는 경우(대칭,회전)의 경우의수를 확인해주고 최댓값을 구하면된다.

 

시간복잡도 20*500*500으로 충분하다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 테트로미노 {

	public static int map[][],n,m;
	public static void main(String[] args)throws Exception {
		
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		 n = Integer.parseInt(st.nextToken());
		 m = Integer.parseInt(st.nextToken());
		map = new int[n+1][m+3];
		for(int i = 1 ; i < n+1 ; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0 ; j < m ;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		int answer = 0;
		for(int i = 1 ; i< n+1 ; i++) {
			for(int j=0; j < m ; j++) {
				for(int k = 0 ; k < 19 ; k++) {
					int res = result(k,i,j);
					answer = answer > res ? answer : res;
				}
			}
		}
		System.out.println(answer);
	}

	private static int result(int k, int i, int j) {
		int resV = map[i][j];
		int ii=0,jj=0;
		if(k==0) {
			ii = i; jj=j+1;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			
			ii = i; jj=j+2;
			
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			 ii = i; jj=j+3;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			return resV;
		} else if(k==1) {
			ii = i+1; jj=j;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			
			ii = i+2; jj=j;
			
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			 ii = i+3; jj=j;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			return resV;
		} else if(k==2) {
			ii = i+1; jj=j;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			
			ii = i; jj=j+1;
			
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			 ii = i+1; jj=j+1;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			return resV;
		} else if(k==3) {
			ii = i+1; jj=j;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			
			ii = i+2; jj=j;
			
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			 ii = i+2; jj=j+1;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			return resV;
		} else if(k==4) {
			ii = i+1; jj=j;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			
			ii = i; jj=j+1;
			
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			 ii = i; jj=j+2;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			return resV;
		} else if(k==5) {
			ii = i; jj=j+1;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			
			ii = i+1; jj=j+1;
			
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			 ii = i+2; jj=j+1;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			return resV;
		} else if(k==6) {
			ii = i+1; jj=j;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			
			ii = i+1; jj=j+1;
			
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			 ii = i+1; jj=j+2;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			return resV;
		} else if(k==7) {
			ii = i+1; jj=j;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			
			ii = i+1; jj=j+1;
			
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			 ii = i+2; jj=j+1;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			return resV;
		} else if(k==8) {
			ii = i; jj=j+1;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			
			ii = i-1; jj=j+1;
			
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			 ii = i-1; jj=j+2;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			return resV;
		} else if(k==9) {
			ii = i+1; jj=j;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			
			ii = i+1; jj=j-1;
			
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			 ii = i+2; jj=j-1;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			return resV;
		} else if(k==10) {
			ii = i; jj=j+1;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			
			ii = i+1; jj=j+1;
			
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			 ii = i+1; jj=j+2;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			return resV;
		} else if(k==11) {
			ii = i; jj=j+1;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			
			ii = i; jj=j+2;
			
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			 ii = i+1; jj=j+1;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			return resV;
		} else if(k==12) {
			ii = i; jj=j+1;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			
			ii = i+1; jj=j+1;
			
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			 ii = i-1; jj=j+1;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			return resV;
		} else if(k==13) {
			ii = i; jj=j+1;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			
			ii = i; jj=j+2;
			
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			 ii = i-1; jj=j+1;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			return resV;
		} else if(k==14) {
			ii = i+1; jj=j;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			
			ii = i+2; jj=j;
			
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			 ii = i+1; jj=j+1;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			return resV;
		} else if(k==15) {
			ii = i; jj=j+1;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			
			ii = i; jj=j+2;
			
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			 ii = i+1; jj=j+2;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			return resV;
		} else if(k==16) {
			ii = i+1; jj=j;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			
			ii = i+2; jj=j;
			
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			 ii = i; jj=j+1;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			return resV;
		} else if(k==17) {
			ii = i; jj=j+1;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			
			ii = i-1; jj=j+1;
			
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			 ii = i-2; jj=j+1;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			return resV;
		} else if(k==18) {
			ii = i; jj=j+1;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			
			ii = i; jj=j+2;
			
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			 ii = i-1; jj=j+2;
			if(!isRange(ii, jj)) {
				return 0;
			} else {
				resV+= map[ii][jj];
			}
			return resV;
		}
		
		else {
			return 0;
		}
	}
	private static boolean isRange(int i,int j) {
		return (i<n+1&&i>=1&&j<m&&j>=0);
	}

}

'알고리즘 > 구현,시뮬' 카테고리의 다른 글

프로그래머스 ) 블록게임  (0) 2020.09.07
Trie 에 대해서 알아봅시다 + Java구현 + [백준] 전화번호 목록 풀이  (6) 2020.09.02
프로그래머스 ) 좌물쇠와 열쇠  (0) 2020.08.16
BOJ - 1560 ) 비숍  (0) 2020.08.12
BOJ - 1477 ) 휴게소 세우기  (0) 2020.08.06
'알고리즘/구현,시뮬' Related Articles more
Comments