MoutainWalking

#include <iostream>

using namespace std;
int t, n;
int arr[102][102];
int visit[102][102];
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
int min1,max1;

class Queue {
public:
	int front, rear;
	int data[20004];
	void reset() {
		front = rear = -1;
	}
	void enQueue(int x) {
		data[++rear] = x;
	}
	int deQueue() {
		return data[++front];
	}
	bool isEmpty() {
		return front == rear ? true : false;
	}
};
Queue q;
void reset() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			visit[i][j] = 0;
		}
	}
}
bool checkBien(int x, int y) {
	if (x >= 1 && x <= n && y >= 1 && y <= n)  return true;
	return false;
}
bool BFS(int min, int max) {
	if (arr[1][1] > max || arr[1][1] < min) return false;
	q.reset();
	reset();
	q.enQueue(1);
	q.enQueue(1);
	visit[1][1] = 1;
	while (!q.isEmpty()) {
		int x = q.deQueue();
		int y = q.deQueue();
		for (int i = 0; i < 4; i++) {
			int newX = x + dx[i];
			int newY = y + dy[i];
			if (checkBien(newX, newY) && visit[newX][newY] == 0 && arr[newX][newY] >= min && arr[newX][newY] <= max) {
				if (newX == n && newY == n) {
					return true;
				}
				q.enQueue(newX);
				q.enQueue(newY);
				visit[newX][newY] = 1;
			}
		}
	}
	return false;
}

int solve(int height) {
	for (int j = min1; j <= max1; j++) {
		int min = j;
		int max = j + height;
		if (BFS(min, max))   return 1;
	}
	return 0;
}

int Try(int left, int right) {
	if (left >= right)  return left;
	int mid = (left + right) / 2;
	if (solve(mid)) {
		Try(left, mid);
	}
	else {
		Try(mid + 1, right);
	}
}
int main() {
	cin >> t;
	for (int tc = 0; tc < t; tc++) {
		cin >> n;
		min1 = 1000000;
		max1 = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				cin >> arr[i][j];
				if (min1 > arr[i][j]) {
					min1 = arr[i][j];
				}
				if (max1 < arr[i][j]) {
					max1 = arr[i][j];
				}
			}
		}

		cout << "#" << tc+1 << " " << Try(0, 110);
	}
	return 0;
}