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