import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class Main{ static int N, M, max, cnt, sum; static boolean[][] visited; static int tail[][]; static ArrayList a = new ArrayList(); static int dr[] = { -1, 0, 1, 0 }; static int dc[] = { 0, 1, 0, -1 }; static int d1x[] = { 0, 0, -1, 0 }; static int d1y[] = { 0, 1, 1, 2 }; static int d2x[] = { 0, 0, 1, 0 }; static int d2y[] = { 0, 1, 1, 2 }; static int d3x[] = { 0, 1, 1, 2 }; static int d3y[] = { 0, 0, -1, 0 }; static int d4x[] = { 0, 1, 1, 2 }; static int d4y[] = { 0, 0, 1, 0 }; public static void solve(int r, int c) { int cnt = 0; sum = 0; for (int i = 0; i < 4; i++) { int nr = r + d1x[i]; int nc = c + d1y[i]; if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue; sum += tail[nr][nc]; cnt++; } if (cnt == 4) max = Math.max(sum, max); cnt = 0; sum = 0; for (int i = 0; i < 4; i++) { int nr = r + d2x[i]; int nc = c + d2y[i]; if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue; sum += tail[nr][nc]; } if (cnt == 4) max = Math.max(sum, max); cnt = 0; sum = 0; for (int i = 0; i < 4; i++) { int nr = r + d3x[i]; int nc = c + d3y[i]; if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue; sum += tail[nr][nc]; } if (cnt == 4) max = Math.max(sum, max); cnt = 0; sum = 0; for (int i = 0; i < 4; i++) { int nr = r + d4x[i]; int nc = c + d4y[i]; if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue; sum += tail[nr][nc]; } if (cnt == 4) max = Math.max(sum, max); cnt = 0; sum = 0; } public static void dfs(int cnt, int r, int c) { if (cnt >= 3) { for (int k = 0; k < a.size(); k++) { sum += tail[a.get(k)[0]][a.get(k)[1]]; } max = Math.max(sum, max); sum = 0; return; } visited[r][c] = true; for (int i = 0; i < 4; i++) { int nr = r + dr[i]; int nc = c + dc[i]; if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue; if (visited[nr][nc]) continue; visited[nr][nc] = true; a.add(new int[] { nr, nc }); dfs(cnt + 1, nr, nc); visited[nr][nc] = false; a.remove(a.size() - 1); } } /* * dfs 4 케이스를 먼저 검사하고 마지막 저거만 따로 해야겠다 시간 복잡도는 완탐일 거 같음 dfs O(nm)아 500^2이네 안 터지겠다 * 1초에 1억이니까 널널하네 완탐 되는구나 */ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); tail = new int[N][M]; for (int i = 0; i < N; i++) { st = new StringTokenizer(br.readLine()); for (int j = 0; j < M; j++) { tail[i][j] = Integer.parseInt(st.nextToken()); } } // TODO dfs 구현 for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { visited = new boolean[N][M]; a.add(new int[] { i, j }); dfs(0, i, j); solve(i, j);//마지막 케이스 따로 구현 a.clear(); } } System.out.println(max); } }

제출 #53298

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: