HDU - 3085 双向BFS + 技巧处理 [kuangbin带你飞]专题二

        题意：有两只鬼，一个男孩女孩被困在迷宫中，男孩每秒可以走三步，女孩只能1步，鬼可以两步且可以通过墙。问男孩女孩是否可以在鬼抓住他们之前会合？

      注意：每秒开始鬼先移动，然后两人开始移动。

     思路：以男孩和女孩为起点进行双向bfs，鬼由于可以穿墙可以直接通过曼哈顿距离判断当前位置是否合法。注意在处理男孩移动的时，必须加入一点技巧，否则处理状态太多就会超时。我用的一种比较笨的方法处理男孩的移动结果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;}如有不当之处欢迎指出！