Untitled

#include<iostream>

using namespace std;

typedef struct{
	int x;
	int y;
}o_xy;

int Map[100][100];
o_xy Queue[100000];

bool Visited[100][100];

int n; // cap cua ma tran dau vao 
int r =-1, f =-1;

void push(o_xy value)
{
	r++;
	Queue[r] = value;
}

o_xy pop()
{
	f++;
	return Queue[f];
}

void reset()
{
	r = f = -1;
	for(int i = 0; i< 100; i++)
		for(int j =0; j< 100; j++)
			Visited[i][j] = false;
}


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

bool BFS(int low, int high)
{
	if(Map[0][0] >= low && Map[0][0] <= high)
	{

	o_xy obj;
	obj.x = 0;
	obj.y = 0;
	push(obj);
	Visited[obj.x][obj.y] = true;

	while(r!=f)
	{
		obj = pop();
		o_xy next;

		for(int i =0; i< 4; i++)
		{
			next.x = obj.x + dx[i];
			next.y = obj.y + dy[i];

			if(next.x >=0 && next.x < n && next.y >=0 && next.y < n )
			{
				if(Map[next.x][next.y] >= low && Map[next.x][next.y] <= high && !Visited[next.x][next.y])
				{
					if(next.x == n - 1 && next.y == n -1)
					{
						return true;
					}
					push(next);
					Visited[next.x][next.y] = true;
				
				}
			}
		}
	}
	}
	return false;
}

bool is_ok(int range, int minnn, int maxxx)
{
	for (int i = minnn; i <= maxxx - range; i++)
	{
		reset();
		if(BFS(i, i+ range))
			return true;
	}
	return false;
}



int main()
{
	//freopen("Text.txt","r",stdin);
	int T, maxx, minn;
	cin >> T;

	for(int tc = 1; tc <= T; tc++)
	{
		cin>>n;
		maxx = 0;
		minn = 110;
		reset();
		for(int i =0; i<n; i++)
		{
			for(int j =0; j< n; j++)
			{
				cin>>Map[i][j];
				if(Map[i][j] > maxx)
				{
					maxx = Map[i][j];
				}
				if(Map[i][j] < minn)
				{
					minn = Map[i][j];
				}
			}
		}

		int left = 0;
		int right = maxx - minn;
		int mid = 0;
		while(left <= right)
		{
			mid = (left + right)/2;
			if(is_ok(mid,minn, maxx))
			{
				right = mid -1;
			}
			else
				left = mid +1;
		}
		cout<<"#"<<tc<<" "<<left<<endl;
	}
	return 0;
}



//
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