Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.7 kB
2
Indexable
Never
#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 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;
	int x = 0; 
	int y = 0;
	push(x,y);
	visit[x][y] = 1;
	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 >= 0 && xx < n && yy >= 0 && yy < n){
			if((map[xx][yy] < low_h || map[xx][yy] > high_h) || visit[xx][yy] == 1) continue;
			else if(map[xx][yy] >= low_h && map[xx][yy] <= high_h ){
				if(xx == n-1 && yy == n-1){
					return true;
				}
				push(xx,yy);
				visit[xx][yy] = 1;
			}
		}
	}
	}
	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 = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				cin >> map[i][j];
				visit[i][j] = 0;
				if(map[i][j] < low){
					low = map[i][j];
				}
				if(map[i][j] > high){
					high = map[i][j];
				}
			}
		}
		cout << min_dis(low,high) << endl;

	}
	return 0;
}