Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.9 kB
1
Indexable
Never
#include <iostream>
#pragma warning (disable:4996)
using namespace std;
#define D 300
int M, N, map[D][D];
int visit[D][D];
int answer, sX, sY;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
struct Point {
	int row, col;
};

Point st;

Point q[1000000];
int front, rear;

void initQ(){
	front = 0;
	rear = 0;
}

void push(Point p){
	q[rear] = p;
	rear++;
}

bool isEmpty(){
	return front == rear;
}

Point pop(){
	Point p = q[front];
	front++;
	return p;
}


void BFS(){
	initQ();
	push(st);
	visit[st.row][st.col] = 1;
	while(!isEmpty()){
		Point p = pop();
		for(int i = 0; i < 4; i++){
			int h = p.row + dx[i];
			int c = p.col + dy[i];
			if(h >= 0 && h < M && c >= 0 && c < N){
				Point tmp;
				if(map[h][c] == 'B' && (visit[h][c] == 0 || visit[p.row][p.col] + 1 < visit[h][c])){
					visit[h][c] = visit[p.row][p.col] + 2;
					tmp.row = h;
					tmp.col = c;
					push(tmp);
				}
				if(map[h][c] == 'E' && (visit[h][c] == 0 || visit[p.row][p.col] + 1 < visit[h][c])){
					visit[h][c] = visit[p.row][p.col] + 1;
					tmp.row = h;
					tmp.col = c;
					push(tmp);
				}
				if(map[h][c] == 'T' && (visit[h][c] == 0 || visit[p.row][p.col] + 1 < visit[h][c])){
					visit[h][c] = visit[p.row][p.col] + 1;
					if(visit[h][c] < answer){
						answer = visit[h][c];
					}
				}
			}
		}
	}
}


int main(){
	freopen("Text.txt", "r", stdin);
	int T; cin >> T; 
	for(int tc = 1; tc <= T; tc++){
		cin >> M >> N;
		for(int i = 0; i < M; i++){
			for(int j = 0; j < N; j++){
				visit[i][j] = 0;
				char c; cin >> c;
				map[i][j] = c;
				if(c == 'Y'){
					st.row = i;
					st.col = j;
				}
			}
		}
		answer = 999;
		BFS();
		cout << "Case #" << tc <<endl;
		if(answer == 999)
			cout << "-1\n";
		else cout << answer - 1 << endl;
	}

	return 0;
}