#include <iostream> #include <queue> #include <vector> #include <cstring> using namespace std; struct Node { int x, y, time, killed; Node(int x, int y, int time, int killed) : x(x), y(y), time(time), killed(killed) {} }; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, 1, 0, -1}; char grid[21][21]; bool visited[21][21][2]; // visited[x][y][killed] 表示在(x, y)位置,是否杀过守卫的状态是否被访问过 int main() { int N, M; cin >> N >> M; for (int i = 1; i <= N; ++i) { for (int j = 1; j <= M; ++j) { cin >> grid[i][j]; } } queue<Node> q; memset(visited, false, sizeof(visited)); int sx, sy, ex, ey; bool foundStart = false, foundEnd = false; // 找到骑士和公主的位置 for (int i = 1; i <= N; ++i) { for (int j = 1; j <= M; ++j) { if (grid[i][j] == 'r') { sx = i; sy = j; foundStart = true; } else if (grid[i][j] == 'a') { ex = i; ey = j; foundEnd = true; } } } if (!foundStart || !foundEnd) { cout << "Impossible" << endl; return 0; } q.push(Node(sx, sy, 0, 0)); visited[sx][sy][0] = true; while (!q.empty()) { Node curr = q.front(); q.pop(); if (curr.x == ex && curr.y == ey) { cout << curr.time << endl; return 0; } for (int i = 0; i < 4; ++i) { int nx = curr.x + dx[i]; int ny = curr.y + dy[i]; if (nx < 1 || nx > N || ny < 1 || ny > M || grid[nx][ny] == '#') continue; if (grid[nx][ny] == 'x') { if (!visited[nx][ny][1]) { q.push(Node(nx, ny, curr.time + 1 + 1, 1)); // 杀死守卫需要额外1个单位时间 visited[nx][ny][1] = true; } } else { int killed = curr.killed || (grid[nx][ny] == 'x'); if (!visited[nx][ny][killed]) { q.push(Node(nx, ny, curr.time + 1, killed)); visited[nx][ny][killed] = true; } } } } cout << "Impossible" << endl; return 0; } /************************************************************** Problem: 1901 User: zhengzihao Language: C++ Result: Accepted Time:13 ms Memory:2080 kb ****************************************************************/