BFS 76分求助
查看原帖
BFS 76分求助
464732
luqyou楼主2022/8/1 14:35
#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy,ex,ey,vis[5001][5001],ans[5001][5001];
char mp[5001][5001];
int dx[]={0,0,0,1,-1};
int dy[]={0,-1,1,0,0};
void bfs(){
	queue<int> x,y;
	x.push(sx);
	y.push(sy);
	vis[sx][sy]=1;
	while(!x.empty()){
		int xx=x.front(),yy=y.front();
		x.pop(),y.pop();
		for(int i=1;i<=4;i++){
			int nx=xx+dx[i],ny=yy+dy[i];
			if(nx>0&&ny&&nx<=n&&ny<=m&&!vis[nx][ny]){
				vis[nx][ny]=1;
				if('A'<=mp[nx][ny]&&mp[nx][ny]<='Z'){
					bool flag=0;
					for(int xxx=1;xxx<=n;xxx++){
						for(int yyy=1;yyy<=n;yyy++){
							if(mp[xxx][yyy]==mp[nx][ny]&&(nx!=xxx||ny!=yyy)){
								nx=xxx,ny=yyy;
								flag=1;
								break;
							}
						}
						if(flag) break;
					}
				}
				x.push(nx);
				y.push(ny);
				ans[nx][ny]=ans[xx][yy]+1;
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%s",mp[i]+1);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(mp[i][j]=='@'){
				sx=i;
				sy=j;
			}
			if(mp[i][j]=='='){
				ex=i;
				ey=j;
			}
			if(mp[i][j]=='#'){
				vis[i][j]=1;
			}
		}
	}
	bfs();
	printf("%d",ans[ex][ey]);
	return 0;
}
/*
in:
10 10
######=###
#ABCDEFGH#
#IJKLMNOP#
#...@....#
#IAKCSPJ.#
#S.BLDHEG#
#.F..MP..#
#..N.....#
#....O...#
##########
out:
5 
*/
2022/8/1 14:35
加载中...