6pts 救救孩子吧QAQ
查看原帖
6pts 救救孩子吧QAQ
1287433
__ycy1124__楼主2024/7/11 08:59

搜索搜不到是为什么

#include<bits/stdc++.h>
using namespace std;
char a[501][501];
bool bj[501][501];
struct Node{
	int x,y,w;
}b[501*501];
int n,m;
int tot=0,ans=-1;
void work(int x){
	if(x/2>=1&&b[x].w<b[x/2].w){
		swap(b[x],b[x/2]);
		work(x/2);
	}
}
void work1(int x){
	if(b[x*2].w<b[x*2+1].w&&x*2+1<=tot&&b[x*2].w<b[x].w){
		swap(b[x*2],b[x]);
		work1(x*2);
	}
	else if(x*2+1<=tot&&b[x*2+1].w<b[x].w){
		swap(b[x*2+1],b[x]);
		work1(x*2+1);
	}
	else if(x*2+1>tot&&x*2==tot&&b[x*2].w<b[x].w){
		swap(b[x*2],b[x]);
		work1(x*2);
	}
	else{
		return;
	}
}
void bfs(int x,int y,int js){
	if(bj[x][y]){
		return;
	}
	bj[x][y]=1;
	//printf("%d %d %d\n",x,y,js);
	if(x==n&&y==m){
		ans=js;
		return;
	}
	if(x-1>=0&&y-1>=0&&!bj[x-1][y-1]){
		if(a[x][y]==char(92)){
			b[++tot]={x-1,y-1,js};
		}
		else{
			b[++tot]={x-1,y-1,js+1};
		}
		work(tot);
	}
	if(x+1<=n&&y-1>=0&&!bj[x+1][y-1]){
		if(a[x+1][y]=='/'){
			b[++tot]={x+1,y-1,js};
		}
		else{
			b[++tot]={x+1,y-1,js+1};
		}
		work(tot);
	}
	if(!bj[x-1][y+1]&&x-1>=0&&y+1<=m){
		if(a[x][y+1]=='/'){
			b[++tot]={x,y+1,js};
		}
		else{
			b[++tot]={x,y+1,js+1};
		}
		work(tot);
	}
	if(!bj[x+1][y+1]&&x+1<=n&&y+1<=m){
		if(a[x+1][y+1]==char(92)){
			b[++tot]={x+1,y+1,js};
		}
		else{
			b[++tot]={x+1,y+1,js+1};
		}
		work(tot);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	if((n+m)%2==1){
		printf("NO SOLUTION");
		return 0;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	b[++tot]={0,0,0};
	while(tot){
		bfs(b[tot].x,b[tot].y,b[tot].w);
		if(ans!=-1){
			cout<<ans;
			return 0;
		}
		swap(b[1],b[tot]);
		tot--;
		work1(1);
	}
	return 0;
}
2024/7/11 08:59
加载中...