#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
struct Node {
int x, y, time, killed;
Node(int x, int y, int time, int killed) : x(x), y(y), time(time), killed(killed) {}
};
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
char grid[21][21];
bool visited[21][21][2]; // visited[x][y][killed] 表示在(x, y)位置,是否杀过守卫的状态是否被访问过
int main() {
int N, M;
cin >> N >> M;
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= M; ++j) {
cin >> grid[i][j];
}
}
queue<Node> q;
memset(visited, false, sizeof(visited));
int sx, sy, ex, ey;
bool foundStart = false, foundEnd = false;
// 找到骑士和公主的位置
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= M; ++j) {
if (grid[i][j] == 'r') {
sx = i;
sy = j;
foundStart = true;
} else if (grid[i][j] == 'a') {
ex = i;
ey = j;
foundEnd = true;
}
}
}
if (!foundStart || !foundEnd) {
cout << "Impossible" << endl;
return 0;
}
q.push(Node(sx, sy, 0, 0));
visited[sx][sy][0] = true;
while (!q.empty()) {
Node curr = q.front();
q.pop();
if (curr.x == ex && curr.y == ey) {
cout << curr.time << endl;
return 0;
}
for (int i = 0; i < 4; ++i) {
int nx = curr.x + dx[i];
int ny = curr.y + dy[i];
if (nx < 1 || nx > N || ny < 1 || ny > M || grid[nx][ny] == '#') continue;
if (grid[nx][ny] == 'x') {
if (!visited[nx][ny][1]) {
q.push(Node(nx, ny, curr.time + 1 + 1, 1)); // 杀死守卫需要额外1个单位时间
visited[nx][ny][1] = true;
}
} else {
int killed = curr.killed || (grid[nx][ny] == 'x');
if (!visited[nx][ny][killed]) {
q.push(Node(nx, ny, curr.time + 1, killed));
visited[nx][ny][killed] = true;
}
}
}
}
cout << "Impossible" << endl;
return 0;
}
/**************************************************************
Problem: 1901
User: zhengzihao
Language: C++
Result: Accepted
Time:13 ms
Memory:2080 kb
****************************************************************/