题意:有两只鬼,一个男孩女孩被困在迷宫中,男孩每秒可以走三步,女孩只能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; }
如有不当之处欢迎指出!