mountain walking code

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);
		}
	}

}