重构一遍就A了。。。但这样效率太低了。。。莫非都要重构？？？QWQ
每一秒男同志bfs3层，女同志bfs1层。注意扩展状态时，要判一下合不合法再扩展，而不是只判扩展的状态合不合法，否则有可能由非法的走到合法的地方。
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#define R register int
const int dx[]={-,,,},dy[]={,,,-};
using namespace std;
inline int g() {
R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;
do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;
}
int n,m,t,tim,cc;
int gx,gy,mx,my,zx,zy,zx1,zy1;
char e[][];
inline int abs(int x) {return x>?x:-x;}
inline bool is(char ch) {return ch=='X'||ch=='Z'||ch=='M'||ch=='G'||ch=='.';}
inline bool ckpos(int x,int y) {
if(x<||x>n||y<||y>m||e[x][y]=='X') return false;
if(*tim>=abs(x-zx)+abs(y-zy)||*tim>=abs(x-zx1)+abs(y-zy1)) return false;
return true;
}
struct node{int x,y; node() {}
node(int xx,int yy) {x=xx,y=yy;}
};
queue<node>q,q1;
inline bool bfs() {
for(R x=;x<=;++x) { queue<node> qt=q; R sz=q.size();
while(sz--) {
node u=qt.front(); qt.pop(); R x=u.x,y=u.y;
if(!ckpos(x,y)) continue;
for(R i=;i<;++i) {
R xx=x+dx[i],yy=y+dy[i];
if(!ckpos(xx,yy)||e[xx][yy]=='M') continue;
if(e[xx][yy]=='G') return true; e[xx][yy]='M';
qt.push(node(xx,yy));
}
} q=qt;
} return false;
}
inline bool bfs1() { queue<node> qt=q1; R sz=q1.size();
while(sz--) {
node u=qt.front(); qt.pop(); R x=u.x,y=u.y;
if(!ckpos(x,y)) continue;
for(R i=;i<;++i) {
R xx=x+dx[i],yy=y+dy[i];
if(!ckpos(xx,yy)||e[xx][yy]=='G') continue;
if(e[xx][yy]=='M') return true; e[xx][yy]='G';
qt.push(node(xx,yy));
}
} q1=qt; return false;
}
signed main() {
t=g(); while(t--) { tim=; cc=;
n=g(),m=g();
for(R i=;i<=n;++i) for(R j=;j<=m;++j) {
while(!is(e[i][j]=getchar())); if(e[i][j]=='M') mx=i,my=j;
else if(e[i][j]=='G') gx=i,gy=j;
else if(e[i][j]=='Z') if(cc) zx1=i,zy1=j; else zx=i,zy=j,++cc;
} while(q.size()) q.pop(); while(q1.size()) q1.pop();
q.push(node(mx,my)); q1.push(node(gx,gy));
while(++tim) {
if(bfs()||bfs1()) {printf("%d\n",tim); break;}
if(q1.empty()||q.empty()) {printf("-1\n"); break;}
}
}
}
2019.04.27
