Untitled
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...