#include<bits/stdc++.h>
using namespace std;
int N, M;
vector<string> grid;
vector<vector<bool>> visited;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int minTime = INT_MAX;
bool isValid(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < M;
}
void dfs(int x, int y, int time) {
if (grid[x][y] == 'a') {
minTime = min(minTime, time);
return;
}
visited[x][y] = true;
char original = grid[x][y];
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (isValid(nx, ny) && !visited[nx][ny]) {
if (grid[nx][ny] == '@') {
dfs(nx, ny, time + 1);
} else if (grid[nx][ny] == 'x') {
grid[nx][ny] = '.'; // Mark the guard as killed
dfs(nx, ny, time + 2); // +1 for moving and +1 for killing the guard
grid[nx][ny] = 'x'; // Restore the original state for backtracking
}
}
}
visited[x][y] = false; // Backtrack
grid[x][y] = original; // Restore the original state for backtracking (optional in this case)
}
int main() {
cin >> N >> M;
grid.resize(N);
visited.resize(N, vector<bool>(M, false));
for (int i = 0; i < N; i++) {
cin >> grid[i];
}
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;
break;
}
}
}
dfs(startX, startY, 0);
if (minTime == INT_MAX) {
cout << "Impossible" << endl;
} else {
cout << minTime << endl;
}
return 0;
}
/**************************************************************
Problem: 1901
User: houlingqi1
Language: C
Result: Compile Error
****************************************************************/