0分BFS求条
查看原帖
0分BFS求条
943498
wangshenluogu楼主2024/8/5 08:39
#include<bits/stdc++.h>
using namespace std; 
int n,m,qx,qy,zx,zy,csx1,csx2,csy1,csy2,vis[301][301],ans=-1;
char a[305][305];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
struct node{
    int x,y,t;
};
queue<node>q;
void bfs(){
	while(!q.empty()){ 
		node zc=q.front();
		if(zc.x==zx&&zc.y==zy){
			ans=max(ans,zc.t); 
			q.pop();
			continue;
		}
		q.pop();
		while(!q.empty()){
			for(int i=0;i<4;i++){
				int nx=zc.x+dx[i];
				int ny=zc.y+dy[i];
				if(nx==csx1&&ny==csy1){
					q.push((node){csx2,csy2,zc.t});
					continue;
				}
				if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]!='#'&&!vis[nx][ny]){
					vis[nx][ny]=1;
					q.push((node){nx,ny,zc.t+1});
				}
			}
		}
	}
}
int main(){
	cin>>n>>m;
	int zcs=1;
	string s;
    for(int i=1;i<=n;i++){
    	cin>>s;
        for(int j=1;j<=m;j++){
            a[i][j]=s[j-1];
    		if(a[i][j]=='@'){
    			qx=i,qy=j;
			}
			if(a[i][j]=='='){
				zx=i,zy=j;
			}
			if(a[i][j]>='A'&&a[i][j]<='Z'){
				if(zcs==1){
					csx1=i,csy1=j;
				}
				if(zcs==2){
					csx2=i,csy2=j;
				}
				zcs++;
			}
		}
	}
	bfs();
	cout<<ans<<endl;
    return 0;
}

本贴禁止无意义回复,请提供有效帮助。

2024/8/5 08:39
加载中...