BFS! 0分求助!玄关!
查看原帖
BFS! 0分求助!玄关!
1046305
WCX6936楼主2024/5/25 21:10

双向求解00分:

#include<bits/stdc++.h>
using namespace std; 
const int N=105;
queue<int>q;
bool ok;
char c[11][11];
int ans,be,en,p[N],deep[N],du[4]={0,1,0,-1},dv[4]={-1,0,1,0};
void bfs(int a){
	int h=a/10,v=a%10;
	for(int i=0;i<4;i++){
		int h1=h+du[i],v1=v+dv[i];
		if(h1<1||h1>10||v1<1||v1>10)continue;
		int t=h1*10+v1;
		if(!p[t]){
			p[t]=p[a];
			q.push(t);
			deep[t]=deep[a]+1;
		}
		else if(p[t]!=p[a]){
			ans=deep[a]+deep[t]+1;
			ok=1;
			return ;
		}
	}
}
int main(){
    for(int i=1;i<=10;i++){
    	for(int j=1;j<=10;j++){
    		cin>>c[i][j];
    		if(c[i][j]=='L')be=i*10+j;
    		if(c[i][j]=='B')en=i*10+j;
		}
	}
	q.push(be);p[be]=1;deep[be]=0;
	q.push(en);p[en]=2;deep[en]=0;
	while(!q.empty()){
		int a=q.front();
		q.pop();
		bfs(a);
		if(ok)break;
	}
	cout<<ans;
	return 0;
}
2024/5/25 21:10
加载中...