Untitled

#include <iostream>
#define MAX 10000
using namespace std;

struct Point{
	int x,y;
};

class Queue{
public:
	Point data[MAX];
	int rear,front;

	Queue(){
		rear=0;
		front=0;
	}
	bool IsEmpty(){
		return rear==front;
	}
	bool IsFull(){
		return front==(rear+1)%MAX;
	}
	void enQueue(int a,int b){
		if(!IsFull()){
			rear=(rear+1)%MAX;
			data[rear].x=a;
			data[rear].y=b;
		}
	}
	Point deQueue(){
		if(!IsEmpty()){
			front=(front+1)%MAX;
			return data[front];
		}else return Point();
	}
};

bool danhdau[101][101];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};

int main()
{
	//freopen("input.txt","r",stdin);
	int TC;
	cin >> TC;
	int mang[101][101];
	for(int tc=1;tc<=TC;tc++)
	{
		int N;
		cin >> N;
		for(int i=1;i<=N;i++)
			for(int j=1;j<=N;j++)
			{
				cin >> mang[i][j];
				danhdau[i][j]=false;
			}
		int docaomax=0;
		for(int i=1;i<=N;i++)
			for(int j=1;j<=N;j++)
				if(mang[i][j]>docaomax) docaomax=mang[i][j];
		bool ans;
		int l=0;
		int r=docaomax;
		while(l<=r)
		{
			int mid = (l+r)/2;
			for(int k=0; k<=docaomax-mid; k++)
			{
				for(int i=1;i<=N;i++)
					for(int j=1;j<=N;j++)
						danhdau[i][j]=false;
				int minx=k;
				int maxx=k+mid;

				Queue walk;
				ans=false;
				if(mang[1][1]>=minx && mang[1][1]<=maxx)
				{
					walk.enQueue(1,1);
					danhdau[1][1]=true;
				}
				while(!walk.IsEmpty() && ans==false)
				{
					Point a=walk.deQueue();

					for(int h=0;h<4;h++)
					{
						int newx=a.x + dx[h];
						int newy=a.y + dy[h];

						if(newx>=1 && newx<=N && newy>=1 && newy<=N && mang[newx][newy]>=minx && mang[newx][newy]<=maxx)
						{
							if(newx==N && newy==N)
							{
								ans=true;
								break;
							}
							if(danhdau[newx][newy]==false)
							{
								danhdau[newx][newy]=true;
								walk.enQueue(newx,newy);
							}
						}
					}
				
				}
				if(ans) break;
			}
			if(ans) r = mid - 1;
			else l = mid + 1;
			
		}
		cout << "#"<<tc<<" "<<l<<endl;
	}
	return 0;
}