46分BFS求助
查看原帖
46分BFS求助
669752
ZnHF楼主2023/3/16 12:53
#include<bits/stdc++.h>
using namespace std;
int n,m;
char maze[400][400];
bool vis[400][400],f;
struct node{
	int x,y,ans;
}s,e,now,nn;
queue<node> q;
void find_next(int xx,int yy){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(maze[i][j]==maze[xx][yy] && i!=xx && j!=yy){
				nn.x=i;
				nn.y=j;
				return;
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>maze[i][j];
			if(maze[i][j]=='@'){
				s.x=i;
				s.y=j;
				vis[i][j]=1;
				q.push(s);
			}
			if(maze[i][j]=='='){
				e.x=i;
				e.y=j;
			}
		}
	}
	while(!q.empty()){
		now=q.front();
		q.pop();
		//cout<<now.x<<" "<<now.y<<" "<<now.ans<<endl;
		if(now.x==e.x && now.y==e.y){
			cout<<now.ans;
			return 0;
		}
		f=0;
		if(now.x+1<=n && !vis[now.x+1][now.y] && maze[now.x+1][now.y]!='#'){
			node t;
			t.x=now.x+1;
			t.y=now.y;
			if(maze[t.x][t.y]>='A' && maze[t.x][t.y]<='Z'){
				find_next(t.x,t.y);
				if(!vis[nn.x][nn.y]){
					vis[nn.x][nn.y]=1;
					nn.ans=now.ans+1;
					q.push(nn);
					f=1;
				}
			}
			if(!f){
				t.ans=now.ans+1;
				vis[t.x][t.y]=1;
				q.push(t);
			}
		}
		f=0;
		if(now.y+1<=m && !vis[now.x][now.y+1] && maze[now.x][now.y+1]!='#'){
			node t;
			t.x=now.x;
			t.y=now.y+1;
			if(maze[t.x][t.y]>='A' && maze[t.x][t.y]<='Z'){
				find_next(t.x,t.y);
				if(!vis[nn.x][nn.y]){
					vis[nn.x][nn.y]=1;
					nn.ans=now.ans+1;
					q.push(nn);
					f=1;
				}
			}
			if(!f){
				t.ans=now.ans+1;
				vis[t.x][t.y]=1;
				q.push(t);
			}
		}
		f=0;
		if(now.x-1>0 && !vis[now.x-1][now.y] && maze[now.x-1][now.y]!='#'){
			node t;
			t.x=now.x-1;
			t.y=now.y;
			if(maze[t.x][t.y]>='A' && maze[t.x][t.y]<='Z'){
				find_next(t.x,t.y);
				if(!vis[nn.x][nn.y]){
					vis[nn.x][nn.y]=1;
					nn.ans=now.ans+1;
					q.push(nn);
					f=1;
				}
			}
			if(!f){
				t.ans=now.ans+1;
				vis[t.x][t.y]=1;
				q.push(t);
			}
		}
		f=0;
		if(now.y-1>0 && !vis[now.x][now.y-1] && maze[now.x][now.y-1]!='#'){
			node t;
			t.x=now.x;
			t.y=now.y-1;
			if(maze[t.x][t.y]>='A' && maze[t.x][t.y]<='Z'){
				find_next(t.x,t.y);
				if(!vis[nn.x][nn.y]){
					vis[nn.x][nn.y]=1;
					nn.ans=now.ans+1;
					q.push(nn);
					f=1;
				}
			}
			if(!f){
				t.ans=now.ans+1;
				vis[t.x][t.y]=1;
				q.push(t);
			}
		}
	}
	return 0;
}
2023/3/16 12:53
加载中...