Untitled

package Mountain_Walking;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int n, res, hmin, hmax;
	static int[][] a, visit, value;
	static int[] dx = { 0, 1, 0, -1 }, dy = { 1, 0, -1, 0 };
	static int[] qx = new int[10000], qy = new int[10000];

	static boolean checkOut(int x, int y) {
		if (x < 0 || x >= n || y < 0 || y >= n)
			return false;
		return true;
	}

	static boolean BFS(int mid) {
		int L = hmin;
		
		while(L <= hmax-mid) {
			int R = L + mid;
			if (a[0][0] < L || a[0][0] > R){
				L++;
			}else{
				visit = new int[n][n];
				visit[0][0] = 1;
				int front = 0, rear = 1;
				qx[front] = 0;
				qy[front] = 0;
				while (front < rear) {
					int xt = qx[front], yt = qy[front];
					if(xt == n-1 && yt == n-1) return true;
					for(int i = 0; i < 4; i++){
						int nx = xt + dx[i], ny = yt + dy[i];
						if(checkOut(nx, ny) && visit[nx][ny] == 0 && a[nx][ny] >= L && a[nx][ny] <= R){
							qx[rear] = nx;
							qy[rear] = ny;
							rear++;
							visit[nx][ny] = 1;
						}
					}
					front++;
				}
				L++;
			}
		}
		
		return false;
	}

	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("input.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

		Scanner scanner = new Scanner(System.in);
		int test = scanner.nextInt();
		for (int t = 1; t <= test; t++) {
			n = scanner.nextInt();
			a = new int[n][n];
			visit = new int[n][n];
			hmin = 110;
			hmax = 0;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					a[i][j] = scanner.nextInt();
					hmin = Math.min(hmin, a[i][j]);
					hmax = Math.max(hmax, a[i][j]);
				}
			}

			int L = 0, R = hmax - hmin;
			while (L <= R) {
				int mid = (L + R) / 2;
				if (BFS(mid)) {
					res = mid;
					R = mid - 1;
				} else {
					L = mid + 1;
				}
			}

			System.out.println("#" + t + " " + res);
		}
		scanner.close();
	}
}