#include <iostream> #include <vector> #include <climits> using namespace std; const int MAXN = 25; char grid[MAXN][MAXN]; int N, M; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, 1, 0, -1}; int minTime = INT_MAX; bool isValid(int x, int y) { return x >= 0 && x < N && y >= 0 && y < M && grid[x][y] != '#'; } void dfs(int x, int y, int time, bool kill) { if (grid[x][y] == 'a') { // 找到公主 minTime = min(minTime, time); return; } if (grid[x][y] == 'x' && !kill) { // 遇到守卫且还未杀死,先杀死守卫 dfs(x, y, time + 1, true); return; } if (grid[x][y] == 'x' && kill) { // 已杀死守卫,可继续移动 grid[x][y] = '@'; // 将守卫位置标记为道路,避免重复杀死 } for (int i = 0; i < 4; i++) { // 向四个方向搜索 int nx = x + dx[i]; int ny = y + dy[i]; if (isValid(nx, ny)) { dfs(nx, ny, time + 1, false); } } } int main() { cin >> N >> M; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { cin >> grid[i][j]; } } int startX, startY; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (grid[i][j] == 'r') { // 找到骑士的起始位置 startX = i; startY = j; } } } dfs(startX, startY, 0, false); // 从骑士的起始位置开始搜索 if (minTime == INT_MAX) { // 如果最短时间没有被更新,说明无法到达公主的位置 cout << "Impossible" << endl; } else { cout << minTime << endl; // 输出最短时间 } return 0; } /************************************************************** Problem: 1901 User: zhengzihao Language: C++ Result: Memory Limit Exceed ****************************************************************/