4116:拯救行动
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200+5;
int R,C,vis[maxn][maxn];
char G[maxn][maxn];
int r0,c0,r1,c1;
struct Point{int x,y,step;bool operator < (const Point& p) const {return step>p.step;}Point(int x,int y,int s): x(x),y(y),step(s){}
};
bool inside(int x,int y)
{return x>=0&&x<R&&y>=0&&y<C;
}
int bfs(int i,int j)
{priority_queue<Point> Q;Q.push(Point(i,j,0));vis[i][j]=1;while(!Q.empty()){int x=Q.top().x,y=Q.top().y,step=Q.top().step;Q.pop();if(x==r1&&y==c1) return step;for(int dx=-1;dx<=1;dx++)for(int dy=-1;dy<=1;dy++){if((dx&&dy)||(!dx&&!dy)) continue;int nx=x+dx;int ny=y+dy;if(!inside(nx,ny)||G[nx][ny]=='#'||vis[nx][ny]) continue;if(G[nx][ny]=='x') Q.push(Point(nx,ny,step+2));else Q.push(Point(nx,ny,step+1));vis[nx][ny]=1;}}return -1;
}
int main()
{int T;cin>>T;while(T--){cin>>R>>C;for(int i=0;i<R;i++)for(int j=0;j<C;j++){cin>>G[i][j];if(G[i][j]=='a') r1=i,c1=j;else if(G[i][j]=='r') r0=i,c0=j; }memset(vis,0,sizeof(vis));int ans=bfs(r0,c0);if(ans==-1) cout<<"Impossible"<<endl;else cout<<ans<<endl;}return 0;
}