BFS+Binary

#include <iostream>
using namespace std;

int map[105][105];
int visit[105][105];
int Qx[150000];
int Qy[150000];
int r = -1, f = -1;
int dx[8]= {1,0,0,-1};
int dy[8]= {0,1,-1,0};
int n, m;
int low, high;

void re_visit(){
	for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				visit[i][j] = 0;
			}
		}
}
void push(int x, int y){
	r++;
	Qx[r] = x;
	Qy[r] = y;

}
void pop(int &x, int &y){
	f++;
	x = Qx[f];
	y = Qy[f];
}

bool haspath(int low_h, int high_h){
	r = f = -1;
	re_visit();
	bool dk1 = false;
	bool dk2 = false;
	int x = 1; 
	int y = 1;
	push(x,y);
	visit[x][y] = 1;
	if(map[x][y] < low_h || map[x][y] > high_h) return false;
	while(r != f){
		pop(x,y);
		for(int i = 0; i < 4; i++){
			int xx = x + dx[i];
			int yy = y + dy[i];
			if(xx >= 1 && xx <= n && yy >= 1 && yy <= n){
			if(map[xx][yy] >= low_h && map[xx][yy] <= high_h && visit[xx][yy] == 0){
				push(xx,yy);
				visit[xx][yy] = 1;
				if(xx == n && yy == n){
					return true;
				}

			}
		}
	}
	}
	return false;
}
bool isok(int range){
	for(int i = low; i <= high - range; i++){
		if(haspath(i, i + range)){
			return true;
		}
	}
	return false;
}
int min_dis(int low, int high){
	int left = 0;
	int right = high - low;
	int mid;
	while(left <= right){
		mid = (right + left)/2;
		if(isok(mid)){
			right = mid-1;
		}
		else left = mid+1;
	}
	return left;
}
int main(){
	freopen("input.txt","r",stdin);
	int T;
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		cin >> n;
		low = 1000;
		high = -1;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				cin >> map[i][j];
				if(map[i][j] < low){
					low = map[i][j];
				}
				if(map[i][j] > high){
					high = map[i][j];
				}
			}
		}
		cout << "#" << tc << " " <<min_dis(low,high) << endl;

	}
	return 0;
}