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