86分bfs求调
查看原帖
86分bfs求调
1207677
MassPoint楼主2024/2/23 14:48
#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy;
char a[301][301];
struct point{
	int x,y,step;
}q[60001];
bool us[301][301];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)	scanf("%s",a[i]+1);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]=='@'){
				sx=i;
				sy=j;
				break;
			}
		}
	}
	int f=1,e=1;
	q[1].x=sx,q[1].y=sy,q[1].step=0,us[sx][sy]=1;
	while(f<=e){
		point u=q[f++];
		for(int i=0;i<4;i++){
			bool p=1;
			point v;
			v.x=u.x+dx[i],v.y=u.y+dy[i],v.step=u.step+1;			
			if(v.x<1||v.x>n||v.y<1||v.y>m)	continue;
			if(a[v.x][v.y]<='Z'&&a[v.x][v.y]>='A'){	
				p=0;
				bool yes=0;		
				for(int i=1;i<=n&&!yes;i++){
					for(int j=1;j<=m;j++){						
						if((v.x!=i||v.y!=j)&&a[i][j]==a[v.x][v.y]){
							v.x=i,v.y=j,yes=1;
							break;
						}
					}
				}
			}
			if(us[v.x][v.y])	continue;
			if(a[v.x][v.y]=='#')	continue;
			if(a[v.x][v.y]=='='){
				cout<<v.step;
				return 0;
			}
			q[++e]=v;
			if(p)	us[v.x][v.y]=1;
		}
	}
	return 0;
}
2024/2/23 14:48
加载中...