//import java.io.*; //import java.lang.*; //import java.util.*; // //public class Main { // static int N, M; // static int[][] arr; // static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1}; // static boolean[][] visited; // static int max; // // public static void main(String[] args) throws IOException { // BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); // StringTokenizer st; // // st = new StringTokenizer(br.readLine()); // // N = Integer.parseInt(st.nextToken()); // M = Integer.parseInt(st.nextToken()); // // arr = new int[N][M]; // // for(int i=0; i void bfs(int x, int y) { // PriorityQueue pq = new PriorityQueue<>(new Comparator() { // // @Override // public int compare(int[] o1, int[] o2) { // return o2[2] - o1[2]; // } // // }); // // int count = 0; // int sum = 0; // // pq.add(new int[]{x, y, arr[x][y]}); // visited[x][y] = true; // // System.out.println(x + " " + y + " " + arr[x][y]); // // // while(true) { // int[] cur = pq.poll(); // int cx = cur[0]; // int cy = cur[1]; // int cn = cur[2]; // // System.out.println(cx+ " " + cy + " " + cn); // // sum += cn; // count++; // visited[cx][cy]=true; // // if(count == 4){ // max = Math.max(max, cn); // return; // } // // for(int i=0; i<4; i++){ // int nx = cx + dx[i]; // int ny = cy + dy[i]; // // if(isValid(nx, ny) && !visited[nx][ny]){ // pq.add(new int[] { nx, ny, (cn+arr[nx][ny]) }); // } // } // } // } // // private static boolean isValid(int x, int y) { // return x > -1 && y > -1 && x < N && y < M; // } //} import java.io.*; import java.lang.*; import java.util.*; public class Main { static int N, M; static int[][] arr; static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1}; static boolean[][] visited; static int max; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer st; st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); arr = new int[N][M]; int bigN = 0; for(int i=0; i void dfs(int x, int y) { PriorityQueue pq = new PriorityQueue<>(new Comparator() { @Override public int compare(int[] o1, int[] o2) { return o2[2] - o1[2]; } }); PriorityQueue pq2 = new PriorityQueue<>(new Comparator() { @Override public int compare(int[] o1, int[] o2) { return o2[2] - o1[2]; } }); int count = 0; int sum = 0; pq.add(new int[]{x, y, arr[x][y]}); visited[x][y] = true; while(true) { if(pq2.isEmpty()) { int[] cur = pq.poll(); int cx = cur[0]; int cy = cur[1]; int cs = cur[2]; count++; visited[cx][cy]=true; if(count == 4){ max = Math.max(max, cs); return; } while(true) { // System.out.println(cx+ " " + cy + " " + cs); for(int i=0; i<4; i++){ int nx = cx + dx[i]; int ny = cy + dy[i]; if(isValid(nx, ny) && !visited[nx][ny]){ pq2.add(new int[] { nx, ny, cs+arr[nx][ny] }); } } if(pq.isEmpty()) break; int[] next = pq.poll(); if(cs == next[2]) { cx = next[0]; cy = next[1]; cs = next[2]; } else break; } pq.clear(); } else { int[] cur = pq2.poll(); int cx = cur[0]; int cy = cur[1]; int cs = cur[2]; count++; visited[cx][cy]=true; if(count == 4){ max = Math.max(max, cs); return; } while(true) { // System.out.println(cx+ " " + cy + " " + cs); for(int i=0; i<4; i++){ int nx = cx + dx[i]; int ny = cy + dy[i]; if(isValid(nx, ny) && !visited[nx][ny]){ pq.add(new int[] { nx, ny, cs+arr[nx][ny] }); } } if(pq2.isEmpty()) break; int[] next = pq2.poll(); if(cs == next[2]) { cx = next[0]; cy = next[1]; cs = next[2]; } else break; } pq2.clear(); } } } private static boolean isValid(int x, int y) { return x > -1 && y > -1 && x < N && y < M; } }

제출 #48913

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: