tank

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.3 kB
1
Indexable
Never
#include <iostream>
using namespace std;
char Qx[100000];
char Qy[100000];
int Qd[100000];
int r = -1, f = -1;
void Push(int x, int y, int d){
	r++;
	Qx[r] = x;
	Qy[r] = y;
	Qd[r] = d;
}
void Pop(int &x, int &y, int &d){
	f++;
	x = Qx[f];
	y = Qy[f];
	d = Qd[f];
}
int dx[4] = {-1,0,0,1};
int dy[4] = {0,1,-1,0};
int BFS(int x, int y, int d){
	Push(x,y, 0);
	while (r != f){
		Pop(x,y,d);
		//check lan can
		for(int i = 0; i  < 4; i++){
			int xx = x + dx[i];
			int yy = y + dy[i];
			if(A[xx][yy] == 'E'){
				Push(xx,yy,d+1);
				A[xx][yy] = 'S';
			}
			else if(A[xx][yy] == 'B'){
				Push(xx,yy,d+2);
				A[xx][yy] = 'S';
			}
			else if(A[xx][yy] == 'T'){
				return d+1;
			}
		}
	}
}
char A[400][400];
int main(){
	freopen ("input.txt", "r", stdin);
	int T;
	cin >> T;
	
	for(int tc = 1; tc <= T; tc++){
		int M, N;
		int yx, yy;
		cin >> M >> N;
		int d;
		//reset
		r = -1;
		f = -1;
		for(int i = 0; i <= M+1; i++){
			for(int j = 0; j <= N+1; j++){
				A[i][j] = 'B';
			}
		}
		for(int i = 1; i <= M; i++){
				cin >> A[i];
		}
		for(int i = 1; i <= M; i++){
			for(int j = 1; j <= N; j++){
				if(A[i][j] == 'Y'){
					yx = i;
					yy = j;
				}
			}
		}
		cout << "Case#" << tc << endl;
		cout << BFS(yx,yy,d) << endl;
	}
	return 0;
}