题意:一个人去救女朋友,两个人都在运动,还有鬼在"扩散",问最少几秒救到女朋友
分析:开两个队列来表示两个人走过的路,一个人走到的地方另一个人已经vis了,那么就是相遇了,鬼就用曼哈顿距离判断.
#includeusing namespace std;const int N = 8e2 + 5;char maze[N][N];int n, m;bool vis[N][N][2];int dx[4] = {-1, 1, 0, 0};int dy[4] = {0, 0, -1, 1};struct Point { int x, y; Point() {} Point(int x, int y) : x (x), y (y) {}};queue que[2];Point mm, gg, gho[2];int get_dis(int x, int y, int ex, int ey) { return abs (ex - x) + abs (ey - y);}bool check2(int x, int y, int tim) { for (int i=0; i<2; ++i) { if (get_dis (x, y, gho[i].x, gho[i].y) <= 2 * tim) return false; } return true;}bool check(int x, int y, int typ) { if (x < 1 || x > n || y < 1 || y > m || maze[x][y] == 'X') return false; else return true;}void init(void) { while (!que[0].empty ()) que[0].pop (); while (!que[1].empty ()) que[1].pop (); memset (vis, false, sizeof (vis));}bool BFS(int typ, int tim) { int sz = que[typ].size (); while (sz--) { Point u = que[typ].front (); que[typ].pop (); if (!check (u.x, u.y, typ) || !check2 (u.x, u.y, tim)) continue; for (int i=0; i<4; ++i) { int tx = u.x + dx[i], ty = u.y + dy[i]; if (!check (tx, ty, typ) || !check2 (tx, ty, tim)) continue; if (vis[tx][ty][typ^1]) return true; if (vis[tx][ty][typ]) continue; vis[tx][ty][typ] = true; que[typ].push (Point (tx, ty)); } } return false;}int run(void) { init (); vis[mm.x][mm.y][0] = true; vis[gg.x][gg.y][1] = true; que[0].push (Point (mm.x, mm.y)); que[1].push (Point (gg.x, gg.y)); int step = 0; while (!que[0].empty () || !que[1].empty ()) { ++step; for (int i=0; i<3; ++i) { if (BFS (0, step)) return step; } if (BFS (1, step)) return step; } return -1;}int main(void) { int T; scanf ("%d", &T); while (T--) { scanf ("%d%d", &n, &m); for (int i=1; i<=n; ++i) { scanf ("%s", maze[i] + 1); } int t = 0; for (int i=1; i<=n; ++i) { for (int j=1; j<=m; ++j) { if (maze[i][j] == 'M') { mm.x = i; mm.y = j; } else if (maze[i][j] == 'G') { gg.x = i; gg.y = j; } else if (maze[i][j] == 'Z') { gho[t].x = i; gho[t++].y = j; } } } printf ("%d\n", run ()); } return 0;}