BFS 45分求助
查看原帖
BFS 45分求助
547658
Shiota_Nagisa楼主2021/12/14 20:48
#include<bits/stdc++.h>
using namespace std;
int x,y,sx,sy;
char a[311][311];
int t[311][311];
bool reach[311][311];
int main(){
    cin>>x>>y;
    queue<int> xx;
	queue<int> yy;
	for(int i=1;i<=x;i++)
	    for(int j=1;j<=y;j++){
		   cin>>a[i][j];
		   if(a[i][j]=='@'){
		      sx=i;
		      sy=j;
		      t[i][j]=0;
		      xx.push(i);
		      yy.push(j);
		    
		    }
	    }
bool kcc=false;
int kcccnt=0;
	while(!xx.empty()){
		int nx=xx.front();
		int ny=yy.front();
		xx.pop();
		yy.pop();
		//cout<<nx<<" "<<ny<<endl;
		if(a[nx][ny]>='A'&&a[nx][ny]<='Z'&&!kcc){
			for(int i=1;i<=x;i++)
			    for(int j=1;j<=y;j++)
			        if(a[i][j]==a[nx][ny]){
			        	//reach[i][j]=true;
			        	t[i][j]=t[nx][ny];
			        	nx=i;
			        	ny=j;
			        	xx.push(i);
			        	yy.push(j);
			        	kcc=true;
			        //	cout<<i<<" "<<j<<endl;
					}
		}
		if(!reach[nx-1][ny]&&a[nx-1][ny]!='#'&&nx-1>=1&&nx-1<=x&&ny>=1&&ny<=y){
			reach[nx-1][ny]=true;
			t[nx-1][ny]=t[nx][ny]+1;
			if(a[nx-1][ny]=='='){
				cout<<t[nx-1][ny]<<endl;
				return 0;
			}
			xx.push(nx-1);
			yy.push(ny);
		}
		if(!reach[nx+1][ny]&&a[nx+1][ny]!='#'&&nx+1>=1&&nx+1<=x&&ny>=1&&ny<=y){
			reach[nx+1][ny]=true;
			t[nx+1][ny]=t[nx][ny]+1;
			if(a[nx+1][ny]=='='){
				cout<<t[nx+1][ny]<<endl;
				return 0;
			}
			xx.push(nx+1);
			yy.push(ny);
		}
		if(!reach[nx][ny+1]&&a[nx][ny+1]!='#'&&nx>=1&&nx<=x&&ny+1>=1&&ny+1<=y){
			reach[nx][ny+1]=true;
			t[nx][ny+1]=t[nx][ny]+1;
			if(a[nx][ny+1]=='='){
				cout<<t[nx][ny+1]<<endl;
				return 0;
			}
			xx.push(nx);
			yy.push(ny+1);
		}
		if(!reach[nx][ny-1]&&a[nx][ny-1]!='#'&&nx>=1&&nx<=x&&ny-1>=1&&ny-1<=y){
			reach[nx][ny-1]=true;
			t[nx][ny-1]=t[nx][ny]+1;
			if(a[nx][ny-1]=='='){
				cout<<t[nx][ny-1]<<endl;
				return 0;
			}
			xx.push(nx);
			yy.push(ny-1);
		}
		if(kcc&&kcccnt){
			kcc=false;
			kcccnt=0;
		}
		else kcccnt++;
	}
	return 0;
}
帮帮菜鸡吧
2021/12/14 20:48
加载中...