题目描述

给定一张N*M的地图，地图中有1个男孩，1个女孩和2个鬼。

字符“.”表示道路，字符“X”表示墙，字符“M”表示男孩的位置，字符“G”表示女孩的位置，字符“Z”表示鬼的位置。

男孩每秒可以移动3个单位距离，女孩每秒可以移动1个单位距离，男孩和女孩只能朝上下左右四个方向移动。

每个鬼占据的区域每秒可以向四周扩张2个单位距离，并且无视墙的阻挡，也就是在第k秒后所有与鬼的曼哈顿距离不超过2k的位置都会被鬼占领。

注意： 每一秒鬼会先扩展，扩展完毕后男孩和女孩才可以移动。

求在不进入鬼的占领区的前提下，男孩和女孩能否会合，若能会合，求出最短会合时间。

输入格式

第一行包含整数T，表示共有T组测试用例。

每组测试用例第一行包含两个整数N和M，表示地图的尺寸。

接下来N行每行M个字符，用来描绘整张地图的状况。（注意：地图中一定有且仅有1个男孩，1个女孩和2个鬼）

输出格式

每个测试用例输出一个整数S，表示最短会合时间。

如果无法会合则输出-1。

每个结果占一行。

数据范围

1<n,m<800

样例

输入样例：

3
5 6
XXXXXX
XZ..ZX
XXXXXX
M.G…
......
5 6
XXXXXX
XZZ..X
XXXXXX
M.....
..G…
10 10
..........
..X.......
..M.X…X.
X.........
.X..X.X.X.
.........X
..XX....X.
X....G…X
…ZX.X…
…Z..X..X
输出样例：

1
1
-1

算法 宽搜

暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！
暴力出奇迹！

C++ 代码

include[HTML_REMOVED]

using namespace std;
typedef pair[HTML_REMOVED] p;
int n,m,t;
char g[1005][1005];
int st[1005][1005];
p ghost[2],boy,girl;
int dx[5]={0,0,1,-1};
int dy[5]={1,-1,0,0};
bool check(int x,int y,int k)
{
if(x<0||x>=n||y<0||y>=m||g[x][y]==’X’) return 0;
for(int i=0;i<2;i)
{
if(abs(x-ghost[i].first)+abs(y-ghost[i].second)<=2*k) return 0;
}
return 1;
}
int bfs()
{
int aabb=0;
queue[HTML_REMOVED] qb,qg;
qb.push(boy);
qg.push(girl);
int step=0;
while(!qb.empty()||!qg.empty())
{
step;
for(int i=0;i<3;i)
{
for(int j=0,len=qb.size();j<len;j)
{
p t=qb.front();
qb.pop();
int x=t.first,y=t.second;
if(!check(x,y,step)) continue;
for(int k=0;k<4;k++)
{
int a=x+dx[k],b=y+dy[k];
if(check(a,b,step)){

                    if(st[a][b]==2) 
                    {
                        return step;
                    }   
                    if(!st[a][b])
                    {
                        st[a][b]=1;
                        qb.push({a,b});
                    }
                }
            }
        }
    }
    for(int i=0;i<1;i++)
    {
        for(int j=0,len=qg.size();j<len;j++)
        {
            p t=qg.front();
            qg.pop();
            int x=t.first,y=t.second;
            if(!check(x,y,step)) continue;
            for(int k=0;k<4;k++)
            {
                int a=x+dx[k],b=y+dy[k];
                if(check(a,b,step))
                {
                    if(st[a][b]==1) 
                    {
                        return step;
                    }
                    if(!st[a][b])
                    {
                        st[a][b]=2;
                        qg.push({a,b});
                    }
                }
            }
        }
    }
}
return -1;

}
int main()
{
cin>>t;
while(t–)
{
cin>>n>>m;
memset(st,0,sizeof(st));
for(int i=0;i[HTML_REMOVED]>g[i];
int cnt=0;
for(int i=0;i<n;i)
{
for(int j=0;j<m;j)
{
if(g[i][j]==’M’) boy={i,j};
else if(g[i][j]==’G’) girl={i,j};
else if(g[i][j]==’Z’) ghost[cnt++]={i,j};
}
}
cout<<bfs()<<endl;
}
}