Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
3.9 kB
2
Indexable
Never
// In Practice, You should use the statndard input/output
// in order to receive a score properly.
// Do not use file input and output. Please be very careful. 
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>

using namespace std;
#define side 3009

int A[side][side], visit[side][side];
int qx[side*side], qy[side*side];
int front, rear;

int i, j, Answer, d;
int n, m;
int xstart, ystart, xC, yC;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};

int maxi (int mm[4]){
	int temp = mm[0];
	for (int mmm = 1; mmm < 4; mmm++){
		if (temp < mm[mmm]){
			temp = mm[mmm];
		}
	}
	return temp;
}

int checkgridfilled (){
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) {
			if (A[i][j] != 0 && visit[i][j] == 0){
				return -1;
			}
		}
	}
	int temp = 0;
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) {
			if (visit[i][j] > temp){
				temp = visit[i][j];
			}
		}
	}
	return temp;
}

void reset (int r, int c) {
	Answer = 0;
	for (i = 0; i < r; i++) {
		for (j = 0; j < c; j++) {
			visit[i][j] = 0;		
		}	
	}
}

void BFS (int x, int y) {
	//Mark visited
	visit[x][y] = 1;

	//Reset queue
	front = 0;
	rear = 0;

	//Enqueue
	qx[rear] = x; 
	qy[rear++] = y;

	while (front != rear) {

		//Dequeue
		int tempX = qx[front];
		int tempY = qy[front++];

		for (d = 0; d < 4; d++) {
			int nextX = tempX + dx[d];
			int nextY = tempY + dy[d];

			if (nextX >= 0 && nextX < n &&
				nextY >= 0 && nextY < m &&
				A[nextX][nextY] == 1 &&				
				visit[nextX][nextY] == 0) {

					visit[nextX][nextY] = visit[tempX][tempY] + 1;
					//if (max < visit[nextX][nextY]) max = visit[nextX][nextY]; //to find max
					//Enqueue
					qx[rear] = nextX; 
					qy[rear++] = nextY;
			}
		}
	}


}

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

	ios::sync_with_stdio(false);

	/* 
	The freopen function below opens input.txt in read only mode and 
	sets your standard input to work with the opened file. 
	When you test your code with the sample data, you can use the function
	below to read in from the sample data file instead of the standard input.
	So. you can uncomment the following line for your local test. But you
	have to comment the following line when you submit for your scores.
	*/

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

	for(test_case = 1; test_case <= T; ++test_case)	{
		cin >> n >> m; 

		reset(n,m);

		cin >> xstart >> ystart;
		xstart--;
		ystart--;

		for (i = 0; i < n; i++) {
			for (j = 0; j < m; j++) {
				cin >> A[i][j];
				if (A[i][j] == 2) {
					xC = i;
					yC = j;
				}
			}
		}

		BFS(xstart, ystart); 

		//for (i = 0; i < n; i++) {
		//	for (j = 0; j < m; j++) {
		//		cout << A[i][j] << " ";
		//	}
		//	cout << endl;
		//}
		//cout << endl;

		//for (i = 0; i < n; i++) {
		//	for (j = 0; j < m; j++) {
		//		cout << visit[i][j] << " ";
		//	}
		//	cout << endl;
		//}
		//cout << endl;

		// Check C is filled?
		//Cach 2: dung for check theo dx[], dy[] & count so canh duoc visit

		int max[4] = {0};
		max[0] = (xC > 0 && visit[xC-1][yC] > 0)? visit[xC-1][yC] : 10000000;
		max[1] = (xC < n-1 && visit[xC+1][yC] > 0)? visit[xC+1][yC] : 10000000;
		max[2] = (yC > 0 && visit[xC][yC-1] > 0)? visit[xC][yC-1] : 10000000;
		max[3] = (yC < m-1 && visit[xC][yC+1] > 0)? visit[xC][yC+1] : 10000000;

		int answer1 = maxi(max);

		if (answer1 == 10000000) {
			answer1 = -1;
		}
		else {
			//answer1++;
			visit[xC][yC] = answer1;
		}

		// Check all grid is filled?
		//cach2: dem so o = 1 tu dau. Khi bfs thi count-- --> 0
		int answer2 = checkgridfilled();


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