-->Nightmare Ⅱ
原题太复杂，直接简单的讲中文吧
Descriptions:
X表示墙
.表示路
M,G表示两个人
Z表示鬼
M要去找G但是有两个鬼（Z）会阻碍他们，每一轮都是M和G先走M能走3步，G能走1步，Z每次向边上2步内变出分身。求所需最短时间。
鬼能穿墙，人不能
Sample Input
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
Sample Output
1
1
-1
题目链接：
https://vjudge.net/problem/HDU-3085
设step为人一共走的轮数，每轮M走3步，G走1步，Z走2步
假设第step轮M、G碰面，碰面的地方为tmp，两个鬼为 zz[i]，i可以是0或1表示两个鬼的编号，设横纵坐标分别为x，y
则tmp和zz[i]的距离为
abs(tmp.x-zz[i].x)+abs(tmp.y-zz[i].y) 这个即是曼哈顿距离
鬼在step轮可以走2*step步
若 abs(tmp.x-zz[i].x)+abs(tmp.y-zz[i].y)<=2*step
那就表示这个地方鬼能来，则这个地方不能碰面
相反若 abs(tmp.x-zz[i].x)+abs(tmp.y-zz[i].y)>2*step
那就表示这个地方鬼不能来，则这个地方能碰面
具体操作见代码
AC代码
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
#define Maxn 1000
using namespace std;
int T,n,m;
int step;//走了几轮
char mp[Maxn][Maxn];//原始地图
int dt[][]= {{,},{-,},{,},{,-}};//四个方向
struct node
{
int x,y;//坐标
};
node now,net;
node zz[],mm,gg;//鬼 M G
queue<node>q[];//分别表示队列M和G
queue<node>qt;//后面函数要用到，过渡
bool judge(node tmp)
{
for(int i=; i<; i++)
{
if(abs(tmp.x-zz[i].x)+abs(tmp.y-zz[i].y)<=step*||mp[tmp.x][tmp.y]=='X'||mp[tmp.x][tmp.y]=='\0')
return false;
}
return true;
}
bool bfs(int pos,int steps,char start,char endd)//队列的编号 M或G可以走的步数 开始标志 结束标志
{
qt=q[pos];//替代，后面要根据不同的steps进行走路
for(int j=; j<steps; j++)//这一轮走几步
{
while(!qt.empty())
{
now=qt.front();
qt.pop();
q[pos].pop();
if(!judge(now))//不满足
continue;
for(int i=; i<; i++)//四个方向
{
net.x=now.x+dt[i][];
net.y=now.y+dt[i][];
if(!judge(net)||mp[net.x][net.y]==start)
continue;
if(mp[net.x][net.y]==endd)//M找到G或G找到M
return true;
mp[net.x][net.y]=start;//将走过的地方表示为开始标志，即M或G已经来过这
q[pos].push(net);
}
}
qt=q[pos];//都向外走了一步，重新初始化qt，再向外走一步
}
return false;
}
int solve()
{
step=;//初始化
while(!q[].empty())//初始化队列，清空
q[].pop();
while(!q[].empty())
q[].pop();
while(!qt.empty())
qt.pop();
q[].push(mm);//分别入队
q[].push(gg);
while(!q[].empty()&&!q[].empty())
{
step++;//走了几轮
if(bfs(,,'M','G')||bfs(,,'G','M'))
return step;
}
return -;
}
int main()
{
scanf("%d",&T);//这里都要用scanf和printf，不然会超时
while(T--)
{
scanf("%d%d",&n,&m);
MEM(mp,'X');//把地图初始化为X
for(int cnt=,i=; i<=n; i++)
{ scanf("%s",&mp[i][]);//一行一行存地图
for(int j=; j<=m; j++)
{
// scanf("%c",&mp[i][j]);
// cin>>mp[i][j];
if(mp[i][j]=='M')
{
mm.x=i;
mm.y=j;
}
if(mp[i][j]=='G')
{
gg.x=i;
gg.y=j;
}
if(mp[i][j]=='Z')
{
zz[cnt].x=i;
zz[cnt].y=j;
cnt++;
}
}
}
printf("%d\n",solve());
}
}