Untitled

 avatar
unknown
plain_text
a year ago
2.7 kB
6
Indexable
#include <iostream>

using namespace std;

int T, N, G;
int R, C;
int ans;
int posX[4];
int posY[4];
bool gold[25][25];
int arr[25][25];
int visited[25][25]; 
int tmp[25][25];

class Queue{
	int front, rear;
	int q[100000];
public:
	Queue();
	void enQueue(int value);
	int deQueue();
	void reset();
	bool is_Empty();
};

Queue::Queue(){
	front = rear = -1;
}
void Queue::enQueue(int value){
	q[++rear] = value;
}
int Queue::deQueue(){
	return q[++front];
}
void Queue::reset(){
	front = rear = -1;
}
bool Queue::is_Empty(){
	return front == rear;
}
int X[4] = {-1, 1, 0, 0};
int Y[4] = {0, 0, -1, 1};

Queue rQueue, cQueue;
int check;

void BFS(int row, int col){
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			if(arr[i][j] == 0){
				visited[i][j] = -5;
			}else{
				visited[i][j] = -1;
			}
		}
	}
	rQueue.reset();
	cQueue.reset();

	visited[row][col] = 0;

	rQueue.enQueue(row);
	cQueue.enQueue(col);

	while(rQueue.is_Empty() == false){
		int cr = rQueue.deQueue();
		int cc = cQueue.deQueue();
		for(int i = 0; i < 4; i++){
			int nr = cr + X[i];
			int nc = cc + Y[i];
			if(nr >= 0 && nr < N && nc >= 0 && nc < N && visited[nr][nc] == -1){
				visited[nr][nc] = visited[cr][cc] + 1;
				rQueue.enQueue(nr);
				cQueue.enQueue(nc);
			}
		}
	}
	for(int i = 0; i < G; i++){
		int a = posX[i];
		int b = posY[i];
		if(visited[a][b] == -1){
			check = 1;
		}
	}
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			if(tmp[i][j] < visited[i][j] && gold[i][j] == false){
				tmp[i][j] = visited[i][j];
			}
		}
	}
}

int main(){
	freopen("input.txt", "rt", stdin);
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		cin >> N >> G;
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				gold[i][j] = false;
			}
		}
		for(int i = 0; i < G; i++){
			cin >> R >> C;
			R--; C--;
			posX[i] = R;
			posY[i] = C;
			gold[R][C] = true;
		}
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				cin >> arr[i][j];
			}
		}
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				if(arr[i][j] == 0){
					tmp[i][j] = -5;
				}else{
					tmp[i][j] = -1;
				}
			}
		}
		for(int i = 0; i < G; i++){
			check = 0;
			BFS(posX[i], posY[i]);
			if(check == 1){
				break;
			}
		}
		int ans = 10000000;
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				if(tmp[i][j] != -5 && tmp[i][j] != -1 && gold[i][j] == false){
					if(ans > tmp[i][j]){
						ans = tmp[i][j];
					}
				}
			}
		}
		cout << "Case #" << tc << endl;
		if( check == 1 || ans == 10000000){
			cout << -1 << endl;
		}else{
			cout << ans << endl;
		}
	}
	return 0;
}
Editor is loading...
Leave a Comment