Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.8 kB
1
Indexable
Never
#include<iostream>
using namespace std;
int n, mountain[100][100];
int front, rear;
int visit[100][100];
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
int queueX[1000000];
int queueY[1000000];

void walk(int x, int y, int start, int end) {
	if (mountain[x][y] < start || mountain[x][y] > end) return;
	front = rear = 0;
	queueX[rear] = x;
	queueY[rear] = y;
	rear++;
	while (front < rear) {
		int xx = queueX[front];
		int yy = queueY[front];
		front++;
		for (int i = 0; i < 4; i++) {
			int _x = xx + dx[i];
			int _y = yy + dy[i];
			if (_x >= 0 && _x < n && _y >= 0 && _y < n) {
				if (visit[_x][_y] == 0) {
					if (mountain[_x][_y] >= start && mountain[_x][_y] <= end) {
						visit[_x][_y] = 1;
						queueX[rear] = _x;
						queueY[rear] = _y;
						rear++;
					}
				}
			}
		}
	}
}

int main(int argc, char** argv)
{
	int test_case;
	int T;


	freopen("input.txt", "r", stdin);
	cin >> T;

	/*
	Read each test case from standard input.
	*/
	for(test_case = 1; test_case <= T; ++test_case)
	{
		cin >> n;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cin >> mountain[i][j];
			}
		}
		int Left = 0, Right = 111;
		while (Left < Right) {
			int mid = (Left + Right) / 2;
			bool check = false;
			for (int i = 0; i <= 110; i++) {
				for (int k = 0; k < n; k++) {
					for (int j = 0; j < n; j++) {
						visit[k][j] = 0;
					}
				}
				visit[0][0] = 1;
				walk(0, 0, i, i + mid);
				if (visit[n - 1][n - 1] == 1) {
					check = true;
					break;
				}
			}
			if (check) Right = mid;
			else Left = mid + 1;
		}


		// Print the answer to standard output(screen).
		cout << "#" << test_case << " " << Left << endl;
	}
	return 0;//Your program should return 0 on normal termination.
}