Untitled

mail@pastecode.io avatar
unknown
plain_text
5 months ago
1.9 kB
1
Indexable
Never
#include <iostream>
using namespace std;

int N, M;
char a[300][300];
int visited[300][300];
int dx[] = {-1, 0,  0, 1};
int dy[] = { 0, 1, -1, 0};
int XStart, YStart, XEnd, YEnd;
int ans;

int attack(int x, int y, int dx, int dy, bool at){
	int x1 = x;
	int y1 = y;
	int cnt = 0;

	while(x1 >= 0 && y1 >= 0 && x1 < N && y1 < M){
		if(at){
			if(a[x1][y1] == 'B') {
				a[x1][y1] = 'Z';
				cnt++;
			}
		}else {
			if(a[x1][y1] == 'Z'){
				 a[x1][y1] = 'B';
				 cnt++;
			}
		}

		x1 = x1 + dx;
		y1 = y1 + dy;
	}
	
	return cnt;
}

void Try(int x, int y, int step){
	if(x == XEnd && y == YEnd){
		if(step < ans) ans = step;
		return;
	}

	visited[x][y] = 1;

	for(int i = 0; i < 4; i++){
		int x1 = x + dx[i];
		int y1 = y + dy[i];

		if(x1 >= 0 && y1 >= 0 && x1 < N && y1 < M && visited[x1][y1] == 0){
			visited[x1][y1] = 1;

			if(a[x1][y1] == 'R' || a[x1][y1] == 'S') break;

			if(a[x1][y1] == 'B'){
				step = step + attack(x1, y1, dx[i], dy[i], 1);
				Try(x1, y1, step);
				step = step - attack(x1, y1, dx[i], dy[i], 0);
			}else {
				step++; 
				Try(x1, y1, step);
				step--;
			}

			visited[x1][y1] = 0;
		}
	}
}

void reset(){
	for(int i = 0; i < 300; i++){
		for(int j = 0; j < 300; j++){
			a[i][j] = ' ';
			visited[i][j] = 0;
		}
	}	
}

int main(){
	// freopen("input.txt", "r", stdin);
	int T; cin >> T;

	for(int tc = 1; tc <= T; tc++){
		cin >> N >> M;

		reset();

		for(int i = 0; i < N; i++){
			for(int j = 0; j < M; j++){
				cin >> a[i][j];
				if(a[i][j] == 'Y'){
					XStart = i;
					YStart = j;
				}
				if(a[i][j] == 'T'){
					XEnd = i;
					YEnd = j;
				}
			}
		}
		
		ans = 1000000;
		Try(XStart, YStart, 0);

		cout << "Case #" << tc << endl;
		if(ans == 1000000){
			cout << -1 << endl;
		}else{
			cout << ans << endl;
		}
	}


	return 0;
}