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; // ㅜ, ㅏ 탐색 (ㅗ, ㅓ는 그리드를 순회하며 다른 위치에서 ㅜ, ㅏ 형태로 체크됨) nkjh(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 nkjh(int c, int r) { // ㅜ shape - 오른쪽과 아래로만 체크 if (r + 2 < W && c + 1 < H) { int sum = map[c][r] + map[c][r+1] + map[c][r+2] + map[c+1][r+1]; max = Math.max(max, sum); } // ㅏ shape - 오른쪽과 아래로만 체크 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); } } }

제출 #54890

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: