import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int max; static int H, W; static int[][] map; static boolean[][] visited; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); H = Integer.parseInt(st.nextToken()); W = Integer.parseInt(st.nextToken()); map = new int[H][W]; for(int c = 0 ; c < H ; c++){ st = new StringTokenizer(br.readLine()); for(int r = 0 ; r < W ; r++){ map[c][r] = Integer.parseInt(st.nextToken()); } } max = 0; visited = new boolean[H][W]; // DFS로 모든 위치에서 탐색 시작 for(int c = 0 ; c < H ; c++){ for(int r = 0 ; r < W ; r++){ visited[c][r] = true; dfs(1, map[c][r], c, r); visited[c][r] = false; // ㅜ, ㅓ, ㅏ, ㅗ 탐색 tetromino(c, r); } } System.out.println(max); } static int[] dc = {-1, 0, 1, 0}; static int[] dr = {0, 1, 0, -1}; public static void dfs(int depth, int sum, int c, int r){ if(depth == 4){ max = Math.max(max, sum); return; } for(int i = 0 ; i < 4 ; i++){ int nc = c + dc[i]; int nr = r + dr[i]; if(nc < 0 || nc >= H || nr < 0 || nr >= W) continue; if(visited[nc][nr]) continue; visited[nc][nr] = true; dfs(depth + 1, sum + map[nc][nr], nc, nr); visited[nc][nr] = false; } } public static void tetromino(int c, int r) { // 오른쪽과 아래 방향으로 한정된 4가지 테트로미노 모양 // 형태 1: ㅜ (오른쪽 및 아래 방향으로 확장) if (c + 1 < H && r + 2 < W) { int sum = map[c][r] + map[c][r+1] + map[c][r+2] + map[c+1][r+1]; max = Math.max(max, sum); } // 형태 2: ㅏ (오른쪽 및 아래 방향으로 확장) if (c + 2 < H && r + 1 < W) { int sum = map[c][r] + map[c+1][r] + map[c+2][r] + map[c+1][r+1]; max = Math.max(max, sum); } // 형태 3: ㅗ의 우측에서 시작하는 ㄱ자형 반대 (오른쪽 및 아래 방향으로 확장) if (c + 1 < H && r + 2 < W) { int sum = map[c+1][r] + map[c+1][r+1] + map[c+1][r+2] + map[c][r+2]; max = Math.max(max, sum); } // 형태 4: ㅓ의 하단에서 시작하는 ㄱ자형 (오른쪽 및 아래 방향으로 확장) if (c + 2 < H && r + 1 < W) { int sum = map[c][r+1] + map[c+1][r+1] + map[c+2][r+1] + map[c+2][r]; max = Math.max(max, sum); } } }

제출 #54894

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: