[삼성기출]백준14500 - 테트로미노

package sw;

import java.io.*;
public class Main14500_테트로미노 {
	static int N,M;
	static int[][] map;
	static int[][][] tetm = {
			{{0,0},{0,1},{0,2},{0,3}},{{0,0},{1,0},{2,0},{3,0}},
			{{0,0},{1,0},{0,1},{1,1}},{{0,0},{1,0},{2,0},{2,1}},
			{{0,0},{1,0},{1,-1},{1,-2}},{{0,0},{0,1},{1,1},{2,1}},
			{{0,0},{1,0},{0,1},{0,2}},{{0,0},{1,0},{1,1},{2,1}},
			{{0,0},{0,1},{-1,1},{-1,2}},{{0,0},{0,1},{0,2},{1,1}},
			{{0,0},{1,0},{1,-1},{1,1}},{{0,0},{0,1},{-1,1},{1,1}},
			{{0,0},{1,0},{2,0},{1,1}},{{0,0},{1,0},{2,0},{2,-1}},
			{{0,0},{0,1},{0,2},{1,2}},{{0,0},{0,1},{1,0},{2,0}},
			{{0,0},{1,0},{1,1},{1,2}},{{0,0},{1,0},{1,-1},{2,-1}},
			{{0,0},{0,1},{1,1},{1,2}}
	};
	static boolean check(int x, int y) {
		if(x>=0 && x<N && y>=0 && y<M)
			return true;
		else return false;
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().trim().split(" ");
		N = Integer.parseInt(input[0]);
		M = Integer.parseInt(input[1]);
		map = new int[N][M];
		String[] str = null;
		for(int i=0; i<N; i++) {
			str = br.readLine().trim().split(" ");
			for(int j=0; j<M; j++) {
				map[i][j] = Integer.parseInt(str[j]);
			}
		}
		int tmp,res=0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				tmp = cal(i,j);
				if(res < tmp) res = tmp; // 이 접점을 시작점으로 할 수 있는 모든 모양의 최댓값
			}
		}
		System.out.println(res);
		
	}
	public static int cal(int x, int y) {
		int dx,dy,tmp,sum = 0;
		boolean flag;
		for(int t=0; t<19; t++) { // 19개 모양 모두 찾는다.
			tmp = 0;
			flag = true; // false: 모양이 끊김, true: 끊기지 않은 완전한 모양.
			for(int d=0; d<4; d++) {
				dx = x + tetm[t][d][0];
				dy = y + tetm[t][d][1];
				if(!check(dx,dy)) { // 모양의 하나의 지점에서라도 끊기면 멈추고 계산하지 않는다.
					flag = false;
					break;
				}
				else tmp+=map[dx][dy];
			}
			if(!flag) continue;
			if(sum < tmp) sum = tmp;
		}
		return sum;
	}
}