#include<bits/stdc++.h> 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}; int minTime = INT_MAX; void dfs(int r, int c, int time, int killCount) { // 检查边界条件和是否已访问 if (r < 0 || r >= N || c < 0 || c >= M || visited[r][c] || grid[r][c] == '#') { return; } // 标记当前位置为已访问 visited[r][c] = true; // 找到公主,更新最短时间 if (grid[r][c] == 'a') { minTime = min(minTime, time + killCount); return; } // 如果是守卫,需要额外花费1个时间单位 if (grid[r][c] == 'x') { killCount++; } // 尝试四个方向的移动 for (int i = 0; i < 4; i++) { int nr = r + dr[i]; int nc = c + dc[i]; dfs(nr, nc, time + 1, killCount); } // 回溯,取消标记已访问 visited[r][c] = false; } int main() { cin >> N >> M; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { cin >> grid[i][j]; } } // 找到骑士的初始位置,并开始深度优先搜索 for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (grid[i][j] == 'r') { dfs(i, j, 0, 0); break; } } } // 输出结果 if (minTime == INT_MAX) { cout << "Impossible" << endl; } else { cout << minTime << endl; } return 0; } /************************************************************** Problem: 1901 User: zhuangsongyu Language: C++ Result: Time Limit Exceed ****************************************************************/