import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private static int[] dx = {0, 0, 1, -1}; private static int[] dy = {1, -1, 0, 0}; private static int N, M; private static int max = 0; private static int[][] map; private static boolean[][] visited; 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()); map = new int[N][M]; visited = new boolean[N][M]; for (int i = 0; i < N; i++) { StringTokenizer row = new StringTokenizer(br.readLine()); for (int j = 0; j < M; j++) map[i][j] = Integer.parseInt(row.nextToken()); } for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { visited[i][j] = true; dfs(i, j, 0, 4); other(i, j); visited[i][j] = false; } } System.out.println(max); } private static void other(int x, int y) { int x1 = x - 1; int y1 = y - 1; int x2 = x + 1; int y2 = y + 1; int result = 0; if (x1 >= 0 && y1 >= 0 && y2 < M) result = Math.max(map[x][y1] + map[x][y] + map[x][y2] + map[x1][y], result); if (x2 < N && y1 >= 0 && y2 < M) result = Math.max(map[x][y1] + map[x][y] + map[x][y2] + map[x2][y], result); if (x1 >= 0 && x2 < N && y2 < M) result = Math.max(map[x1][y] + map[x][y] + map[x2][y] + map[x][y2], result); if (x1 >= 0 && y1 >= 0 && x2 < N) result = Math.max(map[x1][y] + map[x][y] + map[x2][y] + map[x][y1], result); Math.max(result, max); } private static void dfs(int x, int y, int count, int depth) { if (depth == 0) { max = Math.max(max, count); return; } count += map[x][y]; for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 0 || ny < 0 || nx >= N || ny >= M || visited[nx][ny]) continue; visited[nx][ny] = true; dfs(nx, ny, count, depth-1); visited[nx][ny] = false; } } }

제출 #26956

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: