Untitled

 avatar
unknown
plain_text
2 years ago
2.1 kB
3
Indexable
#define _CRT_SECURE_NO_DEPRECATE
#include <iostream>
using namespace std;

char a[305][305];
int visited[305][305];
int N, M;
int x_start, y_start, x_end, y_end;
int dx[] = {-1,  0,  0,  1};
int dy[] = { 0,  1, -1,  0};
int ans;

// Queue
int qx[100000];
int qy[100000];
int front;
int rear;

bool isEmpty() {
	return front == -1;
}

void push(int x, int y) {
	if (front == -1) front = 0;
	rear++;
	qx[rear] = x;
	qy[rear] = y;
}

void pop() {
	if (front >= rear) front = rear = -1;
	else front++;
}

bool check(int x, int y) {
	return x >= 0 && x < N && y >= 0 && y < M;
}

void BFS(int x, int y) {
	front = rear = -1;
	push(x, y);
	visited[x][y] = 0;

	while (!isEmpty()) {
		int topx = qx[front];
		int topy = qy[front];
		pop();

		for (int i = 0; i < 4; i++) { // len phai trai xuong
			int x1 = topx + dx[i];
			int y1 = topy + dy[i];

			if (check(x1, y1) && a[x1][y1] != 'S' && a[x1][y1] != 'R' && visited[x1][y1] > visited[topx][topy]) {
				if (a[x1][y1] == 'E' || a[x1][y1] == 'T') {
					if (visited[x1][y1] > visited[topx][topy] + 1) {
						visited[x1][y1] = visited[topx][topy] + 1;
					}
				}

				if (a[x1][y1] == 'B') {
					if (visited[x1][y1] > visited[topx][topy] + 2) {
						visited[x1][y1] = visited[topx][topy] + 2;
					}
				}

				push(x1, y1);
			}
		}


	}

}

void nhap() {
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> a[i][j];
			if (a[i][j] == 'Y') {
				x_start = i;
				y_start = j;
			}
			if (a[i][j] == 'T') {
				x_end = i;
				y_end = j;
			}
		}
	}
}

void reset() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			visited[i][j] = 1000000;
		}
	}
}

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

	for (int tc = 1; tc <= T; tc++) {
		nhap();
		reset();
		cout << "Case #" << tc << endl;
		BFS(x_start, y_start);
		cout << (visited[x_end][y_end] == 1000000 ? -1 : visited[x_end][y_end]) << endl;
	}

	return 0;
}
Editor is loading...