# mountain walking code

unknown
plain_text
6 months ago
3.0 kB
1
Indexable
Never
```import java.util.Scanner;

class MyQueue{
private int front, rear, max, cnt;
private int[] q;

public MyQueue(int a) {
// TODO Auto-generated constructor stub
front = 0;
rear = -1;
max = a;
cnt = 0;
q = new int[a];
}

public boolean isEmpty() {
return cnt == 0;
}

public void enqueue(int a) {
rear = (rear + 1) % max;
q[rear] = a;
cnt++;
}

public int dequeue() {
int a = q[front];
front = (front + 1) % max;
cnt--;
return a;
}
}

public class Solution {
static int n, ans, max, min;
static int[][] map, d = {{-1, 0, 1, 0}, {0, 1, 0, -1}};
static boolean[] visit;

private static void reset(){

}

private static boolean bfs(int start, int end){
MyQueue qx = new MyQueue(n * n);
MyQueue qy = new MyQueue(n * n);
boolean[][] visit;
if(map[0][0] >= start && map[0][0] <= end){
qx.enqueue(0); qy.enqueue(0);
visit = new boolean[n][n];
visit[0][0] = true;
}
else return false;

int x, y, dx, dy;
while(!qx.isEmpty()){
x = qx.dequeue(); y = qy.dequeue();
for(int i = 0; i < 4; i++){
dx = x + d[0][i]; dy = y + d[1][i];
if(dx >= 0 && dy >= 0 && dx < n && dy < n && !visit[dx][dy] && map[dx][dy] >= start && map[dx][dy] <= end){
visit[dx][dy] = true;
qx.enqueue(dx); qy.enqueue(dy);
if(dx == n - 1 && dy == n - 1) return true;
}
}
}

return false;
}

private static boolean isValid(int mid){
for(int i = min; i <= max - mid; i++){
if(bfs(i, i + mid)) return true;
}
return false;
}

//	private static void solve(int left, int right){
//		if(left < right){
//			int mid = (left + right)/2;
//			if(isValid(mid - left)){
//				ans = mid;
//				solve(left, mid);
//			}
//			else solve(mid + 1, right);
//		}
//	}
private static void solve(int dist, int left, int right){
//		visit[dist] = true;
//		int mid = dist/2;
//		if(!visit[dist]){
//			visit[dist] = true;
//			if(isValid(dist)){
//				ans = mid;
//				solve(mid);
//			}
//			else solve((mid + 1) + mid/2);
//		}

while(!visit[dist]){
visit[dist] = true;
if(isValid(dist)){
ans = right = dist;
//				dist = dist/2;
}

else{
left = dist;
//				dist = dist + (right - dist)/2;
}
dist = left + (right - left)/2;
}
}

public static void main(String[] args) {
// TODO Auto-generated method stub

Scanner sc = new Scanner(System.in);
int testcase = sc.nextInt();
for(int tc = 1; tc <= testcase; tc++){
n = sc.nextInt();
max = 0; min = Integer.MAX_VALUE;
map = new int[n][n];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
map[i][j] = sc.nextInt();
if(map[i][j] < min) min = map[i][j];
if(map[i][j] > max) max = map[i][j];
}
}

ans = -1;
visit = new boolean[max + 1];
solve((max - min)/2, 0, max - min + 1);

System.out.println("#" + tc + " " + ans);
}
}

}
```