13分BFS样例未过求调
查看原帖
13分BFS样例未过求调
943498
wangshenluogu楼主2024/8/13 09:39
#include<bits/stdc++.h>
using namespace std; 
int n,m,qx,qy,zx,zy,csx1,csx2,csy1,csy2,vis[301][301],ans=1e9;
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;
node find(int nx,int ny,int time){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]==a[nx][ny]&&(i!=nx||j!=ny)){
                nx=i;
                ny=j;
                return (node){i,j,time};
            }
        }
    }
}
void bfs(){
	while(!q.empty()){ 
		node zc=q.front();
		if(zc.x==zx&&zc.y==zy){
			ans=min(ans,zc.t); 
			return;
		}
		q.pop();
		for(int i=0;i<4;i++){
			int nx=zc.x+dx[i];
			int ny=zc.y+dy[i];
			if(a[nx][ny]>='A'&&a[nx][ny]<='Y'){
			    q.push((node)find(nx,ny,zc.t));
			}else 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;
	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;
			}
		}
	}
	vis[qx][qy]=1;
	q.push((node){qx,qy,0});
	bfs();
	cout<<ans<<endl;
    return 0;
}

本帖禁止无意义回复,请提供有效帮助。禁止直接给代码。

2024/8/13 09:39
加载中...