#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;
struct Position {
int x, y, time;
Position(int x, int y, int time) : x(x), y(y), time(time) {}
};
int main() {
int N, M;
cin >> N >> M;
vector<string> grid(N);
for (int i = 0; i < N; ++i) {
cin >> grid[i];
}
// Find the positions of the knight and the princess
int knightX, knightY, princessX, princessY;
bool foundKnight = false, foundPrincess = false;
for (int i = 0; i < N && !(foundKnight && foundPrincess); ++i) {
for (int j = 0; j < M && !(foundKnight && foundPrincess); ++j) {
if (grid[i][j] == 'r') {
knightX = i;
knightY = j;
foundKnight = true;
} else if (grid[i][j] == 'a') {
princessX = i;
princessY = j;
foundPrincess = true;
}
}
}
// Define the directions: up, down, left, right
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
// BFS to find the shortest path
vector<vector<bool>> visited(N, vector<bool>(M, false));
queue<Position> q;
q.push(Position(knightX, knightY, 0));
visited[knightX][knightY] = true;
while (!q.empty()) {
Position current = q.front();
q.pop();
if (current.x == princessX && current.y == princessY) {
cout << current.time << endl;
return 0; // Success! Output the time and exit.
}
for (int i = 0; i < 4; ++i) {
int newX = current.x + dx[i];
int newY = current.y + dy[i];
int newTime = current.time + 1;
if (newX >= 0 && newX < N && newY >= 0 && newY < M && !visited[newX][newY]) {
if (grid[newX][newY] == '#') {
continue; // Skip walls
} else if (grid[newX][newY] == 'x') {
newTime++; // Kill the guard
}
visited[newX][newY] = true;
q.push(Position(newX, newY, newTime));
}
}
}
// If BFS completes without finding the princess, output "Impossible"
cout << "Impossible" << endl;
return 0;
}
/**************************************************************
Problem: 1901
User: chenyubo
Language: C++
Result: Accepted
Time:12 ms
Memory:2080 kb
****************************************************************/