HDU - 3085
读题太难了，请看这位大神的翻译：大神的中文题意
思路：
这就是一道暴力BFS模拟啊！！最多再加点A*作为佐料
暴力跑就完事儿，最多算一下在当前点会不会被鬼抓到作为剪枝
在这里我安利一下一篇优秀的题解：大神的题解
嗯？我为什么要在自己的题解里安利别人的题解？因为我的题解是给自个儿看的嗷
代码附：
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define pf push_front
using namespace std;
const int N = 2e5+10;
int n,m,turn;
char mp[888][888];
struct node
{int x,y;
} boy,girl,ghost[2];
int X[5]= {1,-1,0,0};
int Y[5]= {0,0,1,-1};
queue<node>M,G;
bool check(node k)
{for(int i=0; i<2; ++i)if(turn*2>=abs(k.x-ghost[i].x)+abs(k.y-ghost[i].y)||k.x<0||k.x>=n||k.y<0||k.y>=m||mp[k.x][k.y]=='X')return true;return false;
}
bool BFS(bool sex,int steps,char c)
{queue<node>save;for(int done=1; done<=steps; ++done){if(sex)save=M;elsesave=G;while(save.size()){node k=save.front();save.pop();if(sex)M.pop();elseG.pop();if(check(k))continue;for(int i=0; i<4; ++i){node kk=k;kk.x+=X[i];kk.y+=Y[i];if(check(kk)||mp[kk.x][kk.y]==c)continue;if(mp[kk.x][kk.y]=='G'||mp[kk.x][kk.y]=='M')return true;mp[kk.x][kk.y]=c;if(sex)M.push(kk);elseG.push(kk);}}}return false;
}
int work()
{while(M.size())M.pop();while(G.size())G.pop();for(int i=0,cnt=0; i<n; ++i){for(int j=0; j<m; ++j){if(mp[i][j]=='M')boy.x=i,boy.y=j;else if(mp[i][j]=='G')girl.x=i,girl.y=j;else if(mp[i][j]=='Z')ghost[cnt].x=i,ghost[cnt].y=j,cnt=1;}}M.push(boy);G.push(girl);turn=0;while(M.size()&&G.size()){turn++;if(BFS(1,3,'M')||BFS(0,1,'G'))return turn ;}return -1;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);int T;cin>>T;while(T--){cin>>n>>m;for(int i=0; i<n; ++i)cin>>mp[i];cout<<work()<<endl;}return 0;
}