【HDU3085】nightmare2 双向BFS

对于搜索树分支很多且有明确起点和终点的情况时，可以采用双向搜索来减小搜索树的大小。

对于双向BFS来说，与单向最大的不同是双向BFS需要按层扩展，表示可能到达的区域。而单向BFS则是按照单个节点进行扩展，因为只有当前状态。

代码如下：

#include <bits/stdc++.h>

using namespace std;

const int maxn=810;

char mp[maxn][maxn];

int n,m,tot,step,f;

struct node{

	int x,y;

}boy,girl,ghost[2];

queue<node> q[2];//两个队列

bool vis[2][maxn][maxn];//两个表示可达性

void init(){

	tot=0;

	while(q[0].size())q[0].pop();

	while(q[1].size())q[1].pop();

	memset(vis,0,sizeof(vis));

}

void read_and_parse(){

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++){

		scanf("%s",mp[i]+1);

		for(int j=1;j<=m;j++){

			if(mp[i][j]=='M')boy=(node){i,j};

			if(mp[i][j]=='G')girl=(node){i,j};

			if(mp[i][j]=='Z')ghost[tot++]=(node){i,j};

		}

	}

}

bool right(int x,int y){

	if(x<1||x>n||y<1||y>m||mp[x][y]=='X')return 0;

	if(abs(x-ghost[0].x)+abs(y-ghost[0].y)<=step<<1)return 0;

	if(abs(x-ghost[1].x)+abs(y-ghost[1].y)<=step<<1)return 0;

	return 1;

}

const int dx[]={0,0,1,-1};

const int dy[]={1,-1,0,0};

bool bfs(int idx){

	int size=q[idx].size();

	while(size--){

		node now=q[idx].front();q[idx].pop();

		if(!right(now.x,now.y))continue;//查看当前状态是否合法

		for(int i=0;i<4;i++){

			int x=now.x+dx[i],y=now.y+dy[i];

			if(!right(x,y)||vis[idx][x][y])continue;

			if(vis[1-idx][x][y])return 1;

			vis[idx][x][y]=1;

			q[idx].push((node){x,y});

		}

	}

	return 0;

}

void solve(){

	step=0,f=0;

	q[0].push((node){boy.x,boy.y});

	q[1].push((node){girl.x,girl.y});

	while(q[0].size()||q[1].size()){

		++step;

		for(int i=1;i<=3;i++)if(bfs(0)){f=1;break;}//每次扩展三层，表示走三步可能到达的状态

		if(bfs(1)){f=1;break;}

	}

	if(f)printf("%d\n",step);

	else puts("-1");

}

int main(){

	int T;scanf("%d",&T);

	while(T--){

		init();

		read_and_parse();

		solve();

	}

	return 0;

}

巴特西

【HDU3085】nightmare2 双向BFS

最新文章

热门文章