#include<bits/stdc++.h> using namespace std; const int MAXN = 101; int qx, qy, gx, gy; char a[MAXN][MAXN]; int d[MAXN][MAXN]; int fx[4] = {0, 1, 0, -1}; int fy[4] = {1, 0, -1, 0}; void dfs(int x, int y, int k) { if (k >= d[x][y]) return; // 如果当前路径不是最优的,直接返回 d[x][y] = k; // 更新当前位置的最短路径 for (int i = 0; i < 4; i++) { int tx = x + fx[i]; int ty = y + fy[i]; if (tx >= 1 && tx < MAXN && ty >= 1 && ty < MAXN && a[tx][ty] != '#') { if (a[tx][ty] == 'x') { dfs(tx, ty, k + 2); // 遇到守卫,需要额外1单位时间 } else { dfs(tx, ty, k + 1); } } } } int main() { int x, y; // x和y表示地图的尺寸,应该使用其他变量名以避免与坐标变量冲突 cin >> x >> y; for (int i = 0; i < MAXN; i++) { // 初始化d数组为INT_MAX for (int j = 0; j < MAXN; j++) { d[i][j] = INT_MAX; } } for (int i = 1; i <= x; i++) { for (int j = 1; j <= y; j++) { cin >> a[i][j]; if (a[i][j] == 'r') { qx = i; qy = j; } else if (a[i][j] == 'a') { gx = i; gy = j; } } } dfs(qx, qy, 0); int zdbs = d[gx][gy]; if (zdbs == INT_MAX) cout << "Impossible"; else cout << zdbs; return 0; } /************************************************************** Problem: 1901 User: zengdongxin Language: C++ Result: Accepted Time:1966 ms Memory:2772 kb ****************************************************************/