Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.3 kB
0
Indexable
Never
#include<iostream>
using namespace std;
int n;
int arr[105][105];

const int maxS = 1e7;
int Qx[maxS];
int Qy[maxS];
bool visit[105][105];
int maxI;
int minI;
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
int front = -1, rear = -1;
void pop() {
	if (front == maxS - 1) front = -1;
	front++;
}
void push(int x, int y) {
	if (rear == maxS - 1) rear = -1;
	rear++;
	Qx[rear] = x;
	Qy[rear] = y;
}
bool check(int x, int y) {
	return x >= 0 && x < n && y >= 0 && y < n;
}
bool bfs(int l, int r) {
	front =rear = -1;
	push(0, 0);
	visit[0][0] = true;
	if (arr[0][0]<l || arr[0][0]>r) {
		return false;
	}
	else {
		while (front != rear) {
			pop();
			int temx = Qx[front];
			int temy = Qy[front];
			for (int i = 0; i < 4; i++) {
				int stepx = temx + dx[i];
				int stepy = temy + dy[i];
				if (check(stepx, stepy) && !visit[stepx][stepy] && arr[stepx][stepy] >= l && arr[stepx][stepy] <= r) {
					visit[stepx][stepy] = true;
					push(stepx, stepy);
					if (stepx == n - 1 && stepy == n - 1) {
						return true;
					}
				}
			}
		}
	}
	return false;

}
void khoitao() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
		{
			visit[i][j] = false;
		}
	}
}
bool checkK(int k) {
	for (int i = minI; i <= maxI - k; i++) {
		khoitao();
		if (bfs(i, i + k))return true;
	}
	return false;
}
int find(int l, int r) {
	int mid;
	while (r!=l) {
		 mid = (l + r) / 2;
		if (checkK(mid)) {
			r = mid;
		}
		else
			l = mid+1;
	}
	return r;
}
int main() {
	int t;
	cin>>t;
	for(int test =1;test<=t;test++){
		cin >> n;
		maxI = 0;
		minI = 200;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) 
			{
				cin >> arr[i][j];
				if (arr[i][j] > maxI) {
					maxI = arr[i][j];
				}
				if (arr[i][j] < minI) {
					minI = arr[i][j]; 
				}
			}
		}
		int ans = find(0, maxI-minI);
		cout <<"#"<<test<<" "<< ans<<endl;
	}

}





////////////////////////////////////////
4

5

99 85 38 22 55

89 28 33 3 65

99 20 14 67 90

36 27 28 77 31

50 45 12 9 14

2

92 83

19 91

5

61 49 32 34 28

100 65 0 10 89

34 99 40 86 4

10 97 49 21 30

95 33 79 51 65

2

17 60

94 27
//////////////////////
Kq
85
19
50
43