import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N, M; static int[][] board; static int[] dx = {0, 0, -1, 1}; static int[] dy = {1, -1, 0, 0}; static int max = Integer.MIN_VALUE; 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()); board = new int[N][M]; for (int i = 0; i < N; i++) { st = new StringTokenizer(br.readLine()); for (int j = 0; j < M; j++) { board[i][j] = Integer.parseInt(st.nextToken()); } } boolean[][] visit = new boolean[N][M]; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { visit[i][j] = true; dfs(i, j, 1, board[i][j], visit); visit[i][j] = false; } } for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { for (int dir = 0; dir < 4; dir++) { int sum = board[i][j]; boolean check = false; for (int d = 0; d < 4; d++) { int nx = i + dx[d]; int ny = j + dy[d]; if (nx < 0 || nx >= N || ny < 0 || ny >= M) { check = true; break; } if (d != dir) { sum += board[nx][ny]; } } if (!check) { max = Math.max(max, sum); } } } } System.out.println(max); } private static void dfs(int i, int j, int depth, int cur, boolean[][] visit) { if (depth == 4) { max = Math.max(cur, max); return; } for (int dir = 0; dir < 4; dir++) { int nx = i + dx[dir]; int ny = j + dy[dir]; if (nx < 0 || nx >= N || ny < 0 || ny >= M) { continue; } if (visit[nx][ny]) { continue; } visit[nx][ny] = true; dfs(nx, ny, depth + 1, cur + board[nx][ny], visit); visit[nx][ny] = false; } } static class Point { int x, y; public Point(int x, int y) { this.x = x; this.y = y; } } }

제출 #104326

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: