# Untitled

unknown
plain_text
15 days ago
2.0 kB
3
Indexable
Never
```public class Solution {

static int[][] map;
static int maxh = 0;
static int[][] v;
static int[] dx = { -1, 0, 1, 0 };
static int[] dy = { 0, 1, 0, -1 };

public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);

int T = sc.nextInt();

for (int tc = 1; tc <= T; tc++) {
maxh = 0;

int n = sc.nextInt();
map = new int[n][n];

for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map.length; j++) {
map[i][j] = sc.nextInt();
maxh = Math.max(maxh, map[i][j]);
}
}

int high = maxh;
int low = 0;
while (low < high) {
int mid = (low + high) / 2;
if (check_mid(mid)) {
high = mid;
} else {
low = mid + 1;
}
}

System.out.println("#" + tc + " " + high);

map = null;
}
}

private static boolean check_mid(int mid) throws Exception {
for (int i = 0; i + mid <= maxh; i++) {
v = new int[map.length][map.length];
if (bfs(i, i + mid)) {
return true;
}
v = null;
}
return false;
}

private static boolean bfs(int low, int high) throws Exception {
if (map[0][0] > high || map[0][0] < low)
return false;

Queue<NodeCs> qt = new Queue<NodeCs>();
qt.enQueue(new NodeCs(0, 0));
while (!qt.isEmpty()) {
NodeCs tmpN = qt.peek();
qt.deQueue();
if (v[tmpN.i][tmpN.j] == 0) {
v[tmpN.i][tmpN.j] = 1;
for (int i = 0; i < 4; i++) {
int nI = tmpN.i + dx[i];
int nJ = tmpN.j + dy[i];
if (checkBound(nI, nJ)) {
if (map[nI][nJ] >= low) {
if (map[nI][nJ] <= high) {
if (nI == map.length - 1 && nJ == map.length - 1)
return true;
if (v[nI][nJ] == 0)
qt.enQueue(new NodeCs(nI, nJ));
}
}
}
}
}
}
qt = null;
return false;
}

private static boolean checkBound(int nI, int nJ) {
return (nI >= 0 && nI < map.length && nJ >= 0 && nJ < map.length);
}
```