Untitled

mail@pastecode.io avatar
unknown
plain_text
6 months ago
4.3 kB
1
Indexable
Never
#include <iostream>

using namespace std;

int T, N , M, P;
int Hr, Hc;
int arr[55][55];
int visited[55][55];
int X[4] = {-1, 1, 0, 0};
int Y[4] = {0, 0, -1, 1};

class Queue{
	int front, rear;
	int q[10000];
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];
}
bool Queue::is_Empty(){
	return front == rear;
}
void Queue::reset(){
	front = rear = -1;
}

Queue rQueue, cQueue;

bool check(int cr, int cc, int nr, int nc){
	if(arr[cr][cc] == 1){
		if(nr - cr == -1 && cc == nc){
			if(arr[nr][nc] == 2 || arr[nr][nc] == 5 || arr[nr][nc] == 6 || arr[nr][nc] == 1){
				return true;
			}
		}else if(nr == cr && cc - nc == -1){
			if(arr[nr][nc] == 3 || arr[nr][nc] == 6 || arr[nr][nc] == 7 || arr[nr][nc] == 1){
				return true;
			}
		}else if(nr - cr == 1 && cc == nc){
			if(arr[nr][nc] == 2 || arr[nr][nc] == 4 || arr[nr][nc] == 7 || arr[nr][nc] == 1){
				return true;
			}
		}else if(nr == cr && cc - nc == 1){
			if(arr[nr][nc] == 3 || arr[nr][nc] == 4 || arr[nr][nc] == 5 || arr[nr][nc] == 1){
				return true;
			}
		}
	}else if(arr[cr][cc] == 2){
		if(cr - nr == 1 && cc == nc){
			if(arr[nr][nc] == 1 || arr[nr][nc] == 5 || arr[nr][nc] == 6 || arr[nr][nc] == 2){
				return true;
			}
		}else if(cr - nr == -1 && cc == nc){
			if(arr[nr][nc] == 1 || arr[nr][nc] == 4 || arr[nr][nc] == 7 || arr[nr][nc] == 2){
				return true;
			}
		}
	}else if(arr[cr][cc] == 3){
		if(nr == cr && cc - nc == 1){
			if(arr[nr][nc] == 1 || arr[nr][nc] == 4 || arr[nr][nc] == 5 || arr[nr][nc] == 3){
				return true;
			}
		}else if(nr == cr && cc - nc == -1){
			if(arr[nr][nc] == 1 || arr[nr][nc] == 6 || arr[nr][nc] == 7 || arr[nr][nc] == 3){
				return true;
			}
		}
	}else if(arr[cr][cc] == 4){
		if(nr - cr == -1 && cc == nc){
			if(arr[nr][nc] == 1 || arr[nr][nc] == 2 || arr[nr][nc] == 5 || arr[nr][nc] == 6){
				return true;
			}
		}else if(nr == cr && cc - nc == -1){
			if(arr[nr][nc] == 1 || arr[nr][nc] == 3 || arr[nr][nc] == 6 || arr[nr][nc] == 7){
				return true;
			}
		}
	}else if(arr[cr][cc] == 5){
		if(nr - cr == 1 && nc == cc){
			if(arr[nr][nc] == 1 || arr[nr][nc] == 2 || arr[nr][nc] == 4 || arr[nr][nc] == 7){
				return true;
			}
		}else if(nr == cr && cc - nc == -1){
			if(arr[nr][nc] == 1 || arr[nr][nc] == 3 || arr[nr][nc] == 6 || arr[nr][nc] == 7){
				return true;
			}
		}
	}else if(arr[cr][cc] == 6){
		if(nr == cr && cc - nc == 1){
			if(arr[nr][nc] == 1 || arr[nr][nc] == 3 || arr[nr][nc] == 4 || arr[nr][nc] == 5){
				return true;
			}
		}else if(nr - cr == 1 && cc == nc){
			if(arr[nr][nc] == 1 || arr[nr][nc] == 2 || arr[nr][nc] == 4 || arr[nr][nc] == 7){
				return true;
			}
		}
	}else if(arr[cr][cc] == 7){
		if(nr == cr && cc - nc == 1){
			if(arr[nr][nc] == 1 || arr[nr][nc] == 3 || arr[nr][nc] == 4 || arr[nr][nc] == 5){
				return true;
			}
		}else if(nr - cr == -1 && cc == nc){
			if(arr[nr][nc] == 1 || arr[nr][nc] == 2 || arr[nr][nc] == 5 || arr[nr][nc] == 6){
				return true;
			}
		}
	}
	return false;
}

void BFS(int x, int y){
	rQueue.reset();
	cQueue.reset();

	rQueue.enQueue(x);
	cQueue.enQueue(y);

	visited[x][y] = 1;

	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 <= M && arr[nr][nc] != 0 && visited[nr][nc] == 0){
				if(check(cr, cc, nr, nc)){
					visited[nr][nc] = visited[cr][cc] + 1;
					rQueue.enQueue(nr);
					cQueue.enQueue(nc);
				}
			}
		}
	}
}



int main(){
	freopen("input.txt", "rt", stdin);
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		cin >> N >> M >> Hr >> Hc >> P;
		for(int i = 0; i < N; i++){
			for(int j = 0; j < M; j++){
				cin >> arr[i][j];
				visited[i][j] = 0;
			}
		}
		BFS(Hr, Hc);
		int cnt = 0;
		for(int i = 0; i < N; i++){
			for(int j = 0; j < M; j++){
				if(visited[i][j] <= P && visited[i][j] != 0){
					cnt++;
				}
			}
		}
		cout << "Case #" << tc << endl;
		cout << cnt << endl;
	}
	return 0;
}
Leave a Comment