Untitled

mail@pastecode.io avatar
unknown
plain_text
14 days ago
1.8 kB
0
Indexable
Never
#include <iostream>

int T, N, M;
int Mx, My;
int Gx, Gy;
int arr[60][60];
int visited[60][60];

using namespace std;

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;
}
Queue rQueue, cQueue;
int X[4] = {-1, 1, 0, 0};
int Y[4] = {0, 0, -1, 1};

int main(){
	freopen("input.txt" , "rt", stdin);
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		cin >> N >> M;
		for(int i = 0; i < N; i++){
			for(int j = 0; j < M; j++){
				cin >> arr[i][j];
				if(arr[i][j] == 2){
					Mx = i;
					My = j;
				}
			}
		}
		int ans = 0;
		for(int h = 1; h < N; h++){
			for(int i = 0; i < N; i++){
				for(int j = 0; j < M; j++){
					visited[i][j] = 0;
				}
			}
			rQueue.reset();
			cQueue.reset();

			visited[Mx][My] = 1;

			rQueue.enQueue(Mx);
			cQueue.enQueue(My);
			while(rQueue.is_Empty() == false){
				int cr = rQueue.deQueue();
				int cc = cQueue.deQueue();
				for(int i = 0; i < 4; i++){
					for(int j = 1; j <= h; j++){
						int nr = cr + j*X[i];
						int nc = cc + Y[i];
						if(nr >= 0 && nr < N && nc >= 0 && nc < M && visited[nr][nc] == 0 && arr[nr][nc] != 0){
							if(arr[nr][nc] == 3){
								ans = h;
								goto end;
							}else{
								visited[nr][nc] = 1;
								rQueue.enQueue(nr);
								cQueue.enQueue(nc);
							}
						}
					}
				}
			}
		}
end:
		cout << "Case #" << tc << endl;
		cout << ans << endl;
	}
	return 0;
}
Leave a Comment