题目链接：https://vjudge.net/problem/HDU-3085
题意：有两个鬼Z，他们没秒会占领离他的距离小于等于2的位置，有男孩M和女孩G，男孩每秒走3个单位，女孩走1个单位。每次都是鬼先覆盖，再男孩，女孩走。问男孩女孩能否相遇，如果可以则输出所需最小时间，否则输出-1；
思路：对男孩女孩进行双向bfs即可。但要注意鬼先覆盖，可能直接就杀手男孩和女孩了。
//#include<bits/stdc++.h> #include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<queue> using namespace std; typedef long long ll; #define INF 0x7ffffff const int N = 805; int n, m, vis[N][N]; int zx1, zy1, zx2, zy2, mx, my, gx, gy, step; char G[N][N]; int dx[4] = {0, 1, 0, -1}; int dy[4] = {1, 0, -1, 0}; struct node { int x, y; node(int xx, int yy) { x = xx; y = yy; ; } }; bool ok(int x, int y) { if (x < 0 || y < 0 || x >= n || y >= m || G[x][y] == 'X') return false; //看能不能被鬼覆盖 if (abs(x - zx1) + abs(y - zy1) <= 2 * step) return false; if (abs(x - zx2) + abs(y - zy2) <= 2 * step) return false; return true; } int bfs() { memset(vis, 0, sizeof(vis)); //标记状态 0表示未访问 1表示男孩 2表示女孩访问 vis[mx][my] = 1; vis[gx][gy] = 2; step = 0; //初始化时间 queue<node> qm, qg; qm.push(node(mx, my)); qg.push(node(gx, gy)); while (!qm.empty() && !qg.empty()) { step++; //男孩走3步 for (int k = 0; k < 3; k++) { for (int i = 0, len = qm.size(); i < len; i++) { node t = qm.front(); qm.pop(); //判断一下刚出来的点是否能动 if (!ok(t.x, t.y)) continue; for (int j = 0; j < 4; j++) { int fx = t.x + dx[j]; int fy = t.y + dy[j]; if (!ok(fx, fy) || vis[fx][fy] == vis[t.x][t.y]) continue; //看该点符合要求否 避免重复走 if (vis[fx][fy] + vis[t.x][t.y] == 3) { //找到答案 return step; } vis[fx][fy] = vis[t.x][t.y]; qm.push(node(fx, fy)); } } } //女孩走一步 for (int i = 0, len = qg.size(); i < len; i++) { node t = qg.front(); qg.pop(); if (!ok(t.x, t.y)) continue; for (int j = 0; j < 4; j++) { int fx = t.x + dx[j]; int fy = t.y + dy[j]; if (!ok(fx, fy) || vis[fx][fy] == vis[t.x][t.y]) continue; if (vis[fx][fy] + vis[t.x][t.y] == 3) { //找到答案 return step; } vis[fx][fy] = vis[t.x][t.y]; qg.push(node(fx, fy)); } } } return -1; } int main() { int t; cin>>t; while (t--) { cin>>n>>m; for (int i = 0; i < n; i++) { scanf("%s", G[i]); } //找出男女鬼的位置 int cnt = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (G[i][j] == 'Z') { if (!cnt) { zx1 = i; zy1 = j; cnt++; } else { zx2 = i; zy2= j; } } if (G[i][j] == 'M') mx = i, my = j; if (G[i][j] == 'G') gx = i, gy = j; } } printf("%d ", bfs()); } return 0; }