bfs34分 求助各位大佬,(代码有点乱各位大佬就先将就一下)
查看原帖
bfs34分 求助各位大佬,(代码有点乱各位大佬就先将就一下)
637474
gongchuxuansheng楼主2023/3/11 09:10
#include<bits/stdc++.h>
using namespace std;
char mp1[510][510];
int bj[510][510],mp[510][510];
struct dino{
	int x,y,bs,zf;
};
int n,m;
int gox[10]={0,-1,1,-1,1,0,1,-1,0},goy[10]={0,-1,1,1,-1,1,0,0,-1};
deque<dino>q;
int bfs(){
	q.push_back({1,1,0,mp[1][1]});
	while(!q.empty()){
		dino N=q.front();q.pop_front();
		bj[N.x][N.y]=1;
		if(N.x==n&&N.y==m)return N.bs;
		for(int i=1;i<=2;i++){
			int Nx=N.x+gox[i],Ny=N.y+goy[i];
			if(Nx>0&&Nx<=n&&Ny>0&&Ny<=m&&bj[Nx][Ny]!=1&&N.zf==0){
				if(N.zf==mp[Nx][Ny])q.push_front({Nx,Ny,N.bs,0});
				else q.push_back({Nx,Ny,N.bs+1,0});
			}
		}
		for(int i=3;i<=4;i++){
			int Nx=N.x+gox[i],Ny=N.y+goy[i];
			if(Nx>0&&Nx<=n&&Ny>0&&Ny<=m&&bj[Nx][Ny]!=1&&N.zf==1){
				if(N.zf==mp[Nx][Ny])q.push_front({Nx,Ny,N.bs,1});
				else q.push_back({Nx,Ny,N.bs+1,1});
			}
				
		}
		for(int i=5;i<=8;i++){
			int Nx=N.x+gox[i],Ny=N.y+goy[i];
			if(Nx>0&&Nx<=n&&Ny>0&&Ny<=m&&bj[Nx][Ny]!=1){
				if(N.zf!=mp[Nx][Ny])q.push_front({Nx,Ny,N.bs,mp[Nx][Ny]});
				else q.push_back({Nx,Ny,N.bs+1,(N.zf+1)%2});
			}
		}
	}
	return 0;
}
int main(){
	int qx,qy,zx,zy;
	cin>>n>>m;
	if(n==0&&m==0)return 0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>mp1[i][j];
			if(mp1[i][j]=='/')mp[i][j]=1;
			else mp[i][j]=0;
		}
	}
	int BS=bfs();
	if(BS==0)cout<<"NO SOLUTION";
	else cout<<BS;
	return 0;
}
2023/3/11 09:10
加载中...