1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85
| import java.io.*;
public class Solution { static int[][] map = new int[1000][1000]; static int[][] dp = new int[1000][1000]; static int[] dy = {-1,0,1,0}; static int[] dx = {0,1,0,-1}; static int N; public static void main(String[] args) throws IOException { Reader r = new Reader(); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int T = r.nextInt(), tc = 1; while(T-- != 0) { N = r.nextInt(); for(int i = 0; i < N; ++i) for(int j = 0; j < N; ++j) { map[i][j] = r.nextInt(); dp[i][j] = -1; } int ans = -1, num = -1; for(int i = 0; i < N; ++i) for(int j = 0; j < N; ++j){ dp[i][j] = f(i, j); if(dp[i][j] > ans || (dp[i][j] == ans && map[i][j] < num)) { ans = dp[i][j]; num = map[i][j]; } } bw.write("#" + tc++ + " " + num + " " + (ans + 1) + "\n"); } bw.flush(); } static int f(int y, int x) { if(dp[y][x] != -1) return dp[y][x]; for(int i = 0; i < 4; ++i) { int nx = x + dx[i]; int ny = y + dy[i]; if(0<= nx && nx < N && 0 <= ny && ny < N && map[ny][nx] == map[y][x] + 1){ return (dp[y][x] = f(ny, nx))+ 1; } } return dp[y][x] = 0; } static class Reader { final private int BUFFER_SIZE = 1 << 16; private DataInputStream din; private byte[] buffer; private int bufferPointer, bytesRead;
public Reader() { din = new DataInputStream(System.in); buffer = new byte[BUFFER_SIZE]; bufferPointer = bytesRead = 0; }
public int nextInt() throws IOException { int ret = 0; byte c = read(); while (c <= ' ') c = read(); boolean neg = (c == '-'); if (neg) c = read(); do { ret = (ret<<3) + (ret<<1) + (c & 0b1111); } while ((c = read()) >= '0' && c <= '9');
if (neg) return -ret; return ret; }
private void fillBuffer() throws IOException { bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); if (bytesRead == -1) buffer[0] = -1; }
private byte read() throws IOException { if (bufferPointer == bytesRead) fillBuffer(); return buffer[bufferPointer++]; } } }
|