题目描述
给定一张 N×M 的地图,地图中有 1 个男孩,1 个女孩和 2 个鬼。
字符 . 表示道路,字符 X 表示墙,字符 M 表示男孩的位置,字符 G 表示女孩的位置,字符 Z 表示鬼的位置。
男孩每秒可以移动 3 个单位距离,女孩每秒可以移动 1 个单位距离,男孩和女孩只能朝上下左右四个方向移动。
每个鬼占据的区域每秒可以向四周扩张 2 个单位距离,并且无视墙的阻挡,也就是在第 k 秒后所有与鬼的曼哈顿距离不超过 2k 的位置都会被鬼占领。
注意: 每一秒鬼会先扩展,扩展完毕后男孩和女孩才可以移动。
求在不进入鬼的占领区的前提下,男孩和女孩能否会合,若能会合,求出最短会合时间。
输入格式
第一行包含整数 T,表示共有 T 组测试用例。
每组测试用例第一行包含两个整数 N 和 M,表示地图的尺寸。
接下来 N 行每行 M 个字符,用来描绘整张地图的状况。(注意:地图中一定有且仅有 1 个男孩,1 个女孩和 2 个鬼)
输出格式
每个测试用例输出一个整数 S,表示最短会合时间。
如果无法会合则输出 −1。
每个结果占一行。
数据范围
1<n,m<800
样例
输入样例:
3
5 6
XXXXXX
XZ..ZX
XXXXXX
M.G...
......
5 6
XXXXXX
XZZ..X
XXXXXX
M.....
..G...
10 10
..........
..X.......
..M.X...X.
X.........
.X..X.X.X.
.........X
..XX....X.
X....G...X
...ZX.X...
...Z..X..X
输出样例:
1
1
-1
算法1
有几个小技巧,希望你能借鉴
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N=810;
typedef pair<int,int> PII;
char g[N][N];
PII boy,girl,ghost[2];
int vis[N][N];
int n,m,T,step;
bool check(int x,int y){
if(x<0 || x>=n || y<0 || y>=m || g[x][y]=='X') return false;
for(int i=0;i<2;i++)
if(abs(x-ghost[i].first)+abs(y-ghost[i].second)<=2*step) return false;
return true;
}
int dt[]={0,1,0,-1,0};
bool bfs(queue<PII> &q,int who){
q.push({-1,-1});
while(q.size()){
auto t=q.front();
q.pop();
if(t.first==-1) return false;
int x=t.first,y=t.second;
if(!check(x,y))continue;
for(int i=0;i<4;i++){
int a=x+dt[i],b=y+dt[i+1];
if(!check(a,b))continue;
if(vis[a][b] && vis[a][b]!=who) return true;
if(vis[a][b])continue;
vis[a][b]=who;
q.push({a,b});
}
}
}
int bfs(){
memset(vis,0,sizeof vis);
queue<PII>qb,qg;
qb.push(boy), qg.push(girl);
step=1;
for(;qb.size() || qg.size(); step++){
bool meet=0;
meet |= bfs(qb,1) | bfs(qb,1) | bfs(qb,1);
meet |= bfs(qg,2);
if(meet) return step;
}
return -1;
}
int main(){
cin>>T;
while(T--){
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>g[i];
int cnt=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(g[i][j]=='M') boy={i,j};
else if(g[i][j]=='G') girl={i,j};
else if(g[i][j]=='Z') ghost[cnt++]={i,j};
cout<<bfs()<<endl;
}
}