테트로미노 (14500)

1. 문제

문제 링크

2. 풀이

2-1. 조건

1. 테트로미노를 회전, 대칭시킬 수 있다.

2-2. 풀이

회전과 대칭시켜서 만들 수 있는 모든 경우의 테트로미노를
놓을 수 있는 모든 위치에 두어보면 됩니다.
이런 문제는 보통 만들 수 있는 테트로미노를 테이블로 정의하고
반복문으로 모든 위치를 탐색한 다음 종이 위에 테트로미노를 올릴 때
아까 정의한 테이블을 이용합니다.

총 정리를 해보면
1. 회전과 대칭시켜서 만들 수 있는 모든 경우의 테트로미노를 테이블로 만듭니다.
2. 반복문으로 모든 위치를 탐색하며 테이블에 정의된 테트로미노를 올립니다.

3. 전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static int n, m, board[][];
	static final int MIN = 0;
	// 1.회전과 대칭시켜서 만들 수 있는 모든 경우의 테트로미노를 테이블로 만듭니다.
	static int[][][] coverType = {
			{{0,0},{0,1},{1,0},{1,1}},
			{{0,0},{0,1},{0,2},{0,3}},
			{{0,0},{1,0},{2,0},{3,0}},
			{{0,0},{1,0},{2,0},{2,1}},
			{{0,0},{0,1},{0,2},{1,0}},
			{{0,0},{0,1},{1,1},{2,1}},
			{{0,0},{0,1},{0,2},{-1,2}},
			{{0,0},{0,1},{-1,1},{-2,1}},
			{{0,0},{1,0},{1,1},{1,2}},
			{{0,0},{0,1},{1,0},{2,0}},
			{{0,0},{0,1},{0,2},{1,2}},
			{{0,0},{1,0},{1,1},{2,1}},
			{{0,0},{0,1},{-1,1},{-1,2}},
			{{0,0},{1,0},{1,-1},{2,-1}},
			{{0,0},{0,1},{1,1},{1,2}},
			{{0,0},{1,-1},{1,0},{1,1}},
			{{0,0},{1,0},{2,0},{1,1}},
			{{0,0},{0,1},{0,2},{1,1}},
			{{0,0},{1,0},{2,0},{1,-1}}
	};
	
	// 종이위에 테트로미노를 올리는 함수
	static int cover(int type, int y, int x) {
		int ret = 0;
		
		for (int i = 0;  i < 4; i++) {
			int ny = y + coverType[type][i][0];
			int nx = x + coverType[type][i][1];
			
			if (ny < 0 || ny >= n || nx < 0 || nx >= m) return MIN;
			
			ret += board[ny][nx];
		}
		
		return ret;
	}
	
	public static void main(String[] args) throws Exception {
		String[] s = br.readLine().split(" ");
		n = Integer.parseInt(s[0]);
		m = Integer.parseInt(s[1]);
		
		board = new int[n][m];
		
		for (int i = 0; i < n; i++) {
			s = br.readLine().split(" ");
			
			for (int j = 0; j < m; j++) {
				board[i][j] = Integer.parseInt(s[j]);
			}
		}
		
		int ans = MIN;
		
		// 2. 반복문으로 모든 위치를 탐색하며 테이블에 정의된 테트로미노를 올립니다.
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				for (int type = 0; type < 19; type++) {
					ans = Math.max(ans, cover(type, i, j));
				}
			}
		}
		
		bw.write(ans + "");
		bw.close();
	}
}