题目链接:https://vjudge.net/problem/HDU-3085
题意:有两个鬼和两个人和墙,鬼先走,人再走,鬼每走过的地方都会复制一个新鬼,
但新鬼只能等待旧鬼走完一次行程之后,下一次旧鬼再次开始新的行程时旧鬼才能移动,
旧鬼一个行程能走最多两步,M能走三步,G能走一步。
问M和G能不能在被鬼抓住之前相遇,求最短时间。
‘Z’表示鬼。
第一次用曼哈顿距离来真正解决搜索,参考过别人的代码,这份代码感觉还是比较清楚和简单的。
人每次移动一个距离都要进行一次曼哈顿距离的判断,判断人到该点时,是不是在鬼之前先到达,
注意,鬼先移动一个行程,人再移动一个行程。
#include <iostream>
#include <cstring>
#include<vector>
#include <cstdio>
#include<string>
#include <cmath>
#include <map>
#include <queue>
#include <algorithm>
using namespace std; #define inf (1LL << 31) - 1
#define rep(i,j,k) for(int i = (j); i <= (k); i++)
#define rep__(i,j,k) for(int i = (j); i < (k); i++)
#define per(i,j,k) for(int i = (j); i >= (k); i--)
#define per__(i,j,k) for(int i = (j); i > (k); i--) const int N = ;
int mv_x[] = {, , , -};
int mv_y[] = {, -, , };
char mp[N][N]; //原始地图
int mx,my,hx,hy; //男女的坐标
int g_x[],g_y[],g_l; //两个鬼的坐标
int n,m,STEP; struct node{
int x,y;
}; queue <node > que[];
queue <node > qt; inline void init(){
g_l = ;
STEP = ;
} void input(){ init(); rep(i,,n){
rep(j,,m){
cin >> mp[i][j];
if(mp[i][j] == 'M') mx = i, my = j;
else if(mp[i][j] == 'G') hx = i, hy = j;
else if(mp[i][j] == 'Z') g_x[g_l] = i, g_y[g_l++] = j;
}
}
} //是否越界
inline bool check(int x, int y){
return x >= && x <= n && y >= && y <= m;
} //曼哈顿距离判断能不能相遇
inline bool M_dis(int dx,int dy){ rep__(i,,){
if(abs(dx - g_x[i]) + abs(dy - g_y[i]) <= * STEP) return false;
}
return true;
} void show(){ rep(i,,n){
rep(j,,m) cout << mp[i][j];
cout << endl;
}
} bool bfs(int pos, int steps, char me, char another){ rep(i,,steps){ //一个行程走几轮
qt = que[pos]; //把这轮的所有开始点复制给qt while(!qt.empty()){ node tmp = qt.front();
qt.pop();
que[pos].pop(); if(!M_dis(tmp.x,tmp.y)) continue; //刚开始进入bfs判断一次曼哈顿距离,先判断下人没走之前鬼是不是能抓到人 rep__(p,,){ int dx = tmp.x + mv_x[p];
int dy = tmp.y + mv_y[p]; //没越界 不是墙 不是鬼 自己没走过 满足曼哈顿距离
if(check(dx, dy) && mp[dx][dy] != 'X' && mp[dx][dy] != 'Z' && mp[dx][dy] != me
&& M_dis(dx,dy)){ if(mp[dx][dy] == another){ //遇到了另一个人 // cout << "find the position " << dx << " " << dy << endl;
// cout << me <<" find " << mp[dx][dy] << endl;
return true;
} mp[dx][dy] = me; //标记自己走过了这里
que[pos].push(node{ dx, dy });//存在que[]中,表示下一轮的开始点
}
}
}
} return false;
} bool solve(){ while (!que[].empty()) que[].pop();
while (!que[].empty()) que[].pop();
while (!qt.empty()) qt.pop();
//que[0]表示M,que[1]表示G
que[].push(node{ mx, my });
que[].push(node{ hx, hy }); while (!que[].empty() && !que[].empty()){ // && 和 || 其实都可以 &&说明一个人不能走了
//那么另一个人也一定没地方走了 STEP++;//步数加一,其实更好理解为行程加一
if(bfs(, ,'M','G') || bfs(, ,'G','M')) return true; } return false;
} int main(){ ios::sync_with_stdio(false);
cin.tie(); int T;
cin >> T;
while (T--){
cin >> n >> m;
input(); if(solve()) cout << STEP << endl;
else cout << "-1" << endl;
// show();
// cout << endl;
} // getchar(); return ;
}