算法竞赛进阶指南：噩梦（Python）

题目描述：

给定一张 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

题目分析： 

拿到题目后首先思考用什么算法：本题特征很明显 是一个地图类型的题 自然而然想到使用bfs求解

但我们发现本题最棘手的地方是男生，女生和鬼每一轮都需要扩展，这该怎么办呢，我们进一步发现，其实鬼的扩展并不需要展示出来，只需要男女生每次扩展时，检测一下当前点是否是在鬼的扩展范围之内即可

扩展男生女生就较为简单了 只需要正常先扩展一个再扩展另一个即可 每当男生/女生扩展到一个格子 都要判断这个格子能不能走 如果能走 看看是否被女生/男生扩展过 若是扩展过说明他们可以相遇 可以直接返回答案了。否则标记为男生/女生走过该点

具体步骤如下 ：

我们在bfs中按时间t从 1 开始枚举。
如果男孩和女孩都不能再继续扩展，则跳出枚举。
对于男孩，每次扩展三步，并标记扩展到的格子。
如果某个能扩展的格子被女孩扩展过，那么直接返回现在的时间。
对于女孩，每次扩展一步，并标记扩展到的格子。
如果某个能扩展的格子被男孩扩展过，那么直接返回现在的时间。
对于鬼，由于鬼是无视墙的，所以我们只需要在扩展男孩和女孩的时候，判断下有没有进入鬼的占领范围即可。
题目中已经给出了，在第 k 秒后所有与鬼的曼哈顿距离不超过 2k 的位置都会被鬼占领
我们在第 t 秒扩展的时候，判断被扩展的格子是否与某个鬼的曼哈顿距离小于 2t 即可

上代码！ 

 
def check(x,y,step) : # 检查该点能不能走到
    if x<0 or x>=N or y<0 or y>=M : return False
    if Map[x][y] == 'X' : return False
    if abs(x-ghost[0][0]) + abs(y-ghost[0][1]) <= step * 2 : return False
    if abs(x-ghost[1][0]) + abs(y-ghost[1][1]) <= step * 2 : return False
    return True
 
def bfs() :
    qM = [(Mi,Mj)] ; qG = [(Gi,Gj)]
    st = [[0 for i in range(M)]for j in range(N)] # 记录男生/女生走过的情况
    st[Mi][Mj] = 1 ; st[Gi][Gj] = 2 # 记得把初始点放在st中
    step = 0
    while qM or qG : # 扩展男生
        step += 1 # 时间+1
        for n in range(3) : # 注意男生可以一次最多走三步
            lenM = len(qM)
            for _ in range(lenM) :
                if qM == [] : break
                nx,ny = qM.pop(0)
                if not check(nx,ny,step) : continue
                for i,j in [(1,0),(0,1),(-1,0),(0,-1)] :
                    px = nx + i ; py = ny + j 
                    if not check(px,py,step) : continue
                    if st[px][py] == 2 : return step # 如果被女生走到过
                    if not st[px][py] : st[px][py] = 1 ; qM.append((px,py))
                    
        for n in range(1) :
            lenG = len(qG) # 扩展女生
            for _ in range(lenG) :
                if qG == [] : break
                nx,ny = qG.pop(0)
                if not check(nx,ny,step) : continue
                for i,j in [(1,0),(0,1),(-1,0),(0,-1)] :
                    px = nx + i ; py = ny + j 
                    if not check(px,py,step) : continue
                    if st[px][py] == 1 : return step # 如果被男生走到过
                    if not st[px][py] : st[px][py] = 2 ; qG.append((px,py))
    return -1
 
T = int(input())
for _ in range(T) :
    N,M = map(int,input().split())
    Map = []
    for i in range(N) : Map.append(list(input()))
    ghost = [] 
    for i in range(N) :
        for j in range(M) :
            if Map[i][j] == 'M' : Mi,Mj = i,j
            elif Map[i][j] == 'G' : Gi,Gj = i,j
            elif Map[i][j] == 'Z' : ghost.append((i,j))
    print(bfs())