逃离噩梦


解题思路

双向bfs
建立两个队列
男孩一个，女孩一个
同时开始bfs
然后注意判断鬼到不到的了
如果男孩女孩会和
则当前轮数为最短时间

AC代码

#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
int o,n,m,tot,head1,tail1,head2,tail2,pxm[640005],pym[640005],pxg[640005],pyg[640005],pxz[5],pyz[5],c[805][805];
char a[805][805];
int dx[4]={
   0,0,1,-1};
int dy[4]={
   1,-1,0,0};
inline int read()//快读
{
   
	int x = 0, f = 1; char s = getchar();
	while (s < '0' || s > '9') {
    if (s == '-') f = -f; s = getchar(); }
	while (s >= '0' && s <= '9') {
    x = x * 10 + s - '0'; s = getchar(); }
	return x * f;
}
bool check(int x,int y,int z)//判断
{
   
	if(x<1||x>n||y<1||y>m)return false;//出界
	if(a[x][y]=='X')return false;//墙
	for(int i=1;i<=tot;i++)//鬼到不到的了
	 if(abs(x-pxz[i])+abs(y-pyz[i])<=2*z)return false;
	return true;
}
void bfs()
{
   
	while(head1<tail1&&head2<tail2)
	{
   
		o++;
		for(int times=1;times<=3;times++)//3次（男孩）
		{
   
			int end=tail1;
			while(head1<end)
			{
   
				head1++;
				if(!check(pxm[head1],pym[head1],o))continue;
				for(int i=0;i<4;i++)
				{
   
					int xx=pxm[head1]+dx[i],yy=pym[head1]+dy[i];
					if(check(xx,yy,o))
					 if(c[xx][yy]!=1)
					 {
   
					 	if(c[xx][yy]==2){
   printf("%d\n",o);return;}//会和就输出
					 	c[xx][yy]=1;
					 	pxm[++tail1]=xx;pym[tail1]=yy;
					 }
				}
			}
		}
		int end=tail2;//一次（女孩）
		while(head2<end)
		{
   
			head2++;
			if(!check(pxg[head2],pyg[head2],o))continue;
			for(int i=0;i<4;i++)
			{
   
				int xx=pxg[head2]+dx[i],yy=pyg[head2]+dy[i];
				if(check(xx,yy,o))
				 if(c[xx][yy]!=2)
				 {
   
				 	if(c[xx][yy]==1){
   printf("%d\n",o);return;}//会和就输出
				 	c[xx][yy]=2;
				 	pxg[++tail2]=xx;pyg[tail2]=yy;
				 }
			}
		}
	}
	printf("-1\n");
	return;
}
int main()
{
   
	int T;
	T=read();
	while(T--) 
	{
   
		o=tot=head1=tail1=head2=tail2=0;//初值
		memset(c,0,sizeof(c));
		n=read();
		m=read();
		for(int i=1;i<=n;i++)//输入
	 	 for(int j=1;j<=m;j++)
	 	 {
   
	 		a[i][j]=getchar();
	 		while(a[i][j]!='.'&&a[i][j]!='X'&&a[i][j]!='Z'&&a[i][j]!='G'&&a[i][j]!='M')
	 	 	 a[i][j]=getchar();
	 		if(a[i][j]=='M'){
   pxm[++tail1]=i;pym[tail1]=j;c[i][j]=1;}
	 		if(a[i][j]=='G'){
   pxg[++tail2]=i;pyg[tail2]=j;c[i][j]=2;}
	 		if(a[i][j]=='Z'){
   pxz[++tot]=i;pyz[tot]=j;}
	 	 }
		bfs();
	}
	return 0;
}

谢谢