#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
****************************************************************/