Untitled

 avatar
unknown
plain_text
2 years ago
3.2 kB
4
Indexable
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>
#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;
}
Editor is loading...