Untitled

/*
Cho một bản đồ kích thước NxN (2 <= N <= 100), mỗi ô mang giá trị là độ cao của ô đó (0 <= độ cao <= 110). Bác John và bò Bessie đang ở ô trên trái (dòng 1, cột 1) và muốn đi đến cabin (dòng N, cột N). Họ có thể đi sang phải, trái, lên trên và xuống dưới nhưng không thể đi theo đường chéo. Hãy giúp bác John và bò Bessie tìm đường đi sao cho chênh lệch giữa điểm cao nhất và thấp nhất trên đường đi là nhỏ nhất.

 

Input

Dòng 1: Số test case

Dòng 2: N

N dòng tiếp theo chứa N số nguyên, mỗi số cho biết cao độ của một ô.

 

Output

In ra #test case và một số nguyên là chênh lệch độ cao nhỏ nhất.

 

Sample

 

Input

5

5

1 1 3 6 8

1 2 2 5 5

4 4 0 3 3

8 0 2 3 4

4 3 0 2 1

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

 

Output

#1 2

#2 85

#3 9

#4 50

#5 43

#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;
	freopen("input1.txt", "r", stdin);
	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;
	}
	return 0;
}


*/