RT

0分BFS代码:

#include<bits/stdc++.h>
#define min(o,step) o<step?o:step

using namespace std;

const int N=205;
int n,m,T,o,rx,ry,ax,ay;
char a[N][N];
bool vis[N][N];

int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};

struct node{
	
	int x,y,step;
	
	node(){}
	
	node(int xx,int yy,int ss){
		x=xx;
		y=yy;
		step=ss;
	}
	
};

void bfs(int x,int y,int step){
	
	memset(vis,false,sizeof(vis));
	
	queue<node>q;
	q.push(node(x,y,0));
	
	vis[x][y]=1;
	
	while(!q.empty()){
		
		node tmp=q.front();
		q.pop();
		
		
		if(a[tmp.x][tmp.y]=='x')step++;
		
		if(tmp.x==ax&&tmp.y==ay){
			o=min(o,step);
			return;
		}
		
		for(int i=0;i<4;i++){
			
			int wx=tmp.x+dx[i];
			int wy=tmp.y+dy[i];
			
			if(wx<0||wx>=n||wy<0||wy>=m||vis[wx][wy]||a[wx][wy]=='#')continue;
			
			vis[wx][wy]=1;
			
			q.push(node(wx,wy,tmp.step+1));
			
		}
		
	}
	
}

int main(){
	
	cin>>T;
	
	while(T--){
		
		cin>>n>>m;
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				cin>>a[i][j];
				a[i][j]=='r'? rx=i,ry=j : a[i][j]=='a'? ax=i,ay=j:0;
			}
		}
		
		o=INT_MAX;
		
		bfs(rx,ry,0);
		
		o!=INT_MAX? cout<<o<<"\n" : cout<<"Impossible" ;
		
	}
	
	return 0;

}