題意：有兩只鬼，一個男孩女孩被困在迷宮中，男孩每秒可以走三步，女孩只能1步，鬼可以兩步且可以通過墻。問男孩女孩是否可以在鬼抓住他們之前會合？

      注意：每秒開始鬼先移動，然后兩人開始移動。

     思路：以男孩和女孩為起點進行雙向bfs，鬼由于可以穿墻可以直接通過曼哈頓距離判斷當前位置是否合法。注意在處理男孩移動的時，必須加入一點技巧，否則處理狀態(tài)太多就會超時。我用的一種比較笨的方法處理男孩的移動結果TLE了。

AC代碼： 405ms

#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#include<vector>#include<cmath>using namespace std;const int maxn = 800 + 5;char G[maxn][maxn];int vis[2][maxn][maxn];int n, m;struct node{	int x, y;	node() {	} 	node(int x, int y): x(x), y(y){	}};const int dx[] = {0,0,-1,1};const int dy[] = {-1,1,0,0}; bool is_Ghost(int x, int y, int step, vector<node> &p) {	for(int i = 0; i < p.size(); ++i) {		int px = p[i].x, py = p[i].y;		int man = abs(x - px) + abs(y - py); //曼哈頓距離		if(step * 2 >= man) return false; 	}	return true;}queue<node>q[2];vector<node>per, ghost;int bfs(int c, int step) { //共有四個起點 	int num = q[c].size();	while(num--) { //清空上一次的移動位置 		node p = q[c].front();		q[c].pop();		int x = p.x, y = p.y;		if(!is_ghost(x, y, step + 1, ghost)) continue;		for(int i = 0; i < 4; ++i) {			int px = x + dx[i], py = y + dy[i];			if(px < 0 || py < 0 || px >= n || py >= m) continue;			if(vis[c][px][py] || G[px][py] == 'X' || !is_ghost(px, py, step + 1, ghost)) continue;			if(vis[1 - c][px][py]) return 1; //找到對方 			q[c].push(node(px, py));			vis[c][px][py] = 1;		}	}	return 0;}int solve() {	per.clear();	ghost.clear();	while(!q[0].empty()) q[0].pop();	while(!q[1].empty()) q[1].pop(); 	memset(vis, 0, sizeof(vis));	for(int i = 0; i < n; ++i)	for(int j = 0; j < m; ++j) {		if(G[i][j] == 'M') {			per.push_back(node(i, j));			vis[0][i][j] = 1;			q[0].push(node(i, j));		}		else if(G[i][j] == 'G') {			per.push_back(node(i, j));			q[1].push(node(i, j));			vis[1][i][j] = 1;		}		else if(G[i][j] == 'Z') {			ghost.push_back(node(i, j));		}	}	for(int i = 0; i < 2; ++i) {		if(!is_ghost(per[i].x, per[i].y, 1, ghost)) return -1;	}	int step = -1;	while(!q[0].empty() && !q[1].empty()) {		++step;		for(int i = 0; i < 3; ++i) {			if(bfs(0, step)) return step + 1; 		} 		if(bfs(1, step)) return step + 1;	}	return -1;}int main() {	int T;	scanf("%d", &T);	while(T--) {		scanf("%d%d", &n, &m);		for(int i = 0; i < n; ++i) scanf("%s", G[i]);		PRintf("%d/n", solve());	}	return 0;}如有不當之處歡迎指出！