BFS求问
查看原帖
BFS求问
811069
What__can__I__say楼主2024/6/18 22:49

蒟蒻不懂BFS,请问这个代码输出为什么总是莫名其妙多1,多2,或是有什么低级错误?

#include<bits/stdc++.h>
#define int long long
#define il inline
#define pii pair<int,int>
#define mk make_pair
#define mod 100000000
using namespace std;
il int rd(){
    int jya=0,tl=1;char jyt=getchar();
    while(!isdigit(jyt)){if(jyt=='-')tl=-1;jyt=getchar();}
    while(isdigit(jyt)){jya=(jya<<1)+(jya<<3)+(jyt-'0');jyt=getchar();}
    return jya*tl;
}
il void wr(int jjy){
    if(jjy<0)putchar('-'),jjy=-jjy;
    if(jjy>9)wr(jjy/10);
    putchar(jjy%10+48);
}
il int max(int x,int y){return x>=y?x:y;}
il int min(int x,int y){return x<=y?x:y;}
const int JYAAKIOI=1145141919810;
struct node{
	int x,y,s,g;
	il bool operator<(const node& a)const{
		return s<a.s;
	}
};
int n,m,x,y,xx,yy,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1},ans=JYAAKIOI,to[1086][1086],too[1086][1086];
char a[1086][1086];
bool vis[1086][1086][2];
priority_queue<node>q;
signed main(){
	freopen("jytwcnm.in","r",stdin);
	freopen("jytwcnm.out","w",stdout);
	n=rd();m=rd();
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cin>>a[i][j];
			if(a[i][j]=='C'){
				x=i;
				y=j;
			}
			if(a[i][j]=='D'){
				xx=i;
				yy=j;
			}
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(a[i][j]=='#')to[i][j]=i+1;
			else to[i][j]=to[i-1][j];//往上走会到哪个点 
		}
	}
	for(int i=n;i>=1;--i){
		for(int j=1;j<=m;++j){
			if(a[i][j]=='#')too[i][j]=i-1;
			else too[i][j]=too[i+1][j];//往下走会到哪个点 
		}
	}
	q.push((node){too[x][y],y,0,0});//0向下,1向上 
	vis[too[x][y]][y][0]=1;
	//cout<<xx<<" "<<yy;
	while(!q.empty()){
		int nowx=q.top().x,nowy=q.top().y,now=q.top().s,nowg=q.top().g;//行,列,反转次数,重力方向 
		//cout<<nowx<<" "<<nowy<<" "<<now<<" "<<nowg<<endl;
		q.pop();
		if(nowx==xx&&nowy==yy){
			wr(now);
			return 0;
		}
		if(nowy-1>=1&&a[nowx][nowy-1]!='#'){//向左走 
			if(nowg&1){//重力向上 
				if(nowx>=xx&&to[nowx][nowy-1]<=xx&&nowy==yy){
					wr(now);
					return 0;
				}
				if(!vis[to[nowx][nowy-1]][nowy-1][nowg]&&to[nowx][nowy-1]>=1&&to[nowx][nowy-1]<=n){
					vis[to[nowx][nowy-1]][nowy-1][nowg]=1;
					q.push((node){to[nowx][nowy-1],nowy-1,now,nowg});
				}
			}
			else{//重力向下 
				if(nowx<=xx&&too[nowx][nowy-1]>=xx&&nowy==yy){
					wr(now);
					return 0;
				}
				if(!vis[too[nowx][nowy-1]][nowy-1][nowg]&&too[nowx][nowy-1]>=1&&too[nowx][nowy-1]<=n){
					vis[too[nowx][nowy-1]][nowy-1][nowg]=1;
					q.push((node){too[nowx][nowy-1],nowy-1,now,nowg});
				}
			}
		}
		if(nowy+1<=m&&a[nowx][nowy+1]!='#'){//向右走 
			if(nowg&1){//重力向上 
				if(nowx>=xx&&to[nowx][nowy+1]<=xx&&nowy==yy){
					wr(now);
					return 0;
				}
				if(!vis[to[nowx][nowy+1]][nowy+1][nowg]&&to[nowx][nowy+1]>=1&&to[nowx][nowy+1]<=n){
					vis[to[nowx][nowy+1]][nowy+1][nowg]=1;
					q.push((node){to[nowx][nowy+1],nowy+1,now,nowg});
				}
			}
			else{//重力向下 
				if(nowx<=xx&&to[nowx][nowy+1]>=xx&&nowy==yy){
					wr(now);
					return 0;
				}
				if(!vis[too[nowx][nowy+1]][nowy+1][nowg]&&too[nowx][nowy+1]>=1&&too[nowx][nowy+1]<=n){
					vis[too[nowx][nowy+1]][nowy+1][nowg]=1;
					q.push((node){too[nowx][nowy+1],nowy+1,now,nowg});
				}
			}
		}
		if(nowg&1){//重力向上时向下走 
			if(nowy==yy&&nowx<=xx&&too[nowx][nowy]>=xx){//如果下落时碰到D 
				wr(now+1);
				return 0;
			}
			if(too[nowx][nowy]>=1&&too[nowx][nowy]<=n){
				if(!vis[too[nowx][nowy]][nowy][1-nowg]){
					vis[too[nowx][nowy]][nowy][1-nowg]=1;
					q.push((node){too[nowx][nowy],nowy,now+1,1-nowg});
				}
			}
		}
		if(!nowg&1){//重力向下时向上走 
			if(nowy==yy&&nowx>=xx&&to[nowx][nowy]<=xx){
				//if(now==486)now=484;
				wr(now+1);
				return 0;
			}
			if(to[nowx][nowy]>=1&&to[nowx][nowy]<=n){
				if(!vis[to[nowx][nowy]][nowy][1-nowg]){
					vis[to[nowx][nowy]][nowy][1-nowg]=1;
					q.push((node){to[nowx][nowy],nowy,now+1,1-nowg});
				}
			}
		}
	}
	//cout<<too[4][5];
	wr(-1);
	return 0;
}
2024/6/18 22:49
加载中...