#include <iostream> #include <vector> #include <queue> #include <cstring> using namespace std; const int MAXN = 20; char grid[MAXN][MAXN]; bool visited[MAXN][MAXN]; int N, M; int dr[] = {-1, 1, 0, 0}; // 上下左右四个方向 int dc[] = {0, 0, -1, 1}; struct Node { int r, c, time, killCount; Node(int r, int c, int time, int killCount) : r(r), c(c), time(time), killCount(killCount) {} }; int bfs(int startR, int startC) { queue<Node> q; memset(visited, false, sizeof(visited)); q.push(Node(startR, startC, 0, 0)); visited[startR][startC] = true; while (!q.empty()) { Node currentNode = q.front(); q.pop(); if (grid[currentNode.r][currentNode.c] == 'a') { return currentNode.time + currentNode.killCount; } for (int i = 0; i < 4; ++i) { int nextR = currentNode.r + dr[i]; int nextC = currentNode.c + dc[i]; int nextTime = currentNode.time + 1; int nextKillCount = currentNode.killCount; if (grid[nextR][nextC] == 'x') { nextKillCount++; } if (nextR >= 0 && nextR < N && nextC >= 0 && nextC < M && !visited[nextR][nextC] && grid[nextR][nextC] != '#') { visited[nextR][nextC] = true; q.push(Node(nextR, nextC, nextTime, nextKillCount)); } } } return -1; // 表示无法到达公主 } int main() { cin >> N >> M; for (int i = 0; i < N; ++i) { for (int j = 0; j < M; ++j) { cin >> grid[i][j]; if (grid[i][j] == 'r') { int time = bfs(i, j); if (time == -1) { cout << "Impossible" << endl; } else { cout << time << endl; } } } } return 0; } /************************************************************** Problem: 1901 User: zhuangsongyu Language: C++ Result: Wrong Answer ****************************************************************/