原题链接： https://www.acwing.com/problem/content/179/

题目描述

给定一张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

题解

这是一种BFS新的扩展方式，先把男孩每一步能扩展的区域标记为1，同时女孩每一步能扩展的区域标记为2，男孩与女孩能相遇的条件就是走过相同的区域。因为要维护每一步所有的区域。因此采用下面的方式

#include <iostream> #include <queue> #include <algorithm> #include <cstring> using namespace std; typedef pair<int, int> PII; const int N = 810; char g[N][N]; int n, m; int st[N][N]; PII ghost[2]; bool check(int x, int y, int step) { 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) <= step * 2) return false; return true; } int bfs() { memset(st, 0, sizeof st); int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1}; PII boy, girl; 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}; } } queue<PII> qb, qg; qb.push(boy); qg.push(girl); int step = 0; while(qb.size() || qg.size()) { step++; for(int i = 0; i < 3; i++) { for(int j = 0, len = qb.size(); j < len; j++) { auto t = qb.front(); qb.pop(); int x = t.first, y = t.second; if(!check(x, y, step)) continue; //这里要判断一下，因为第一次入队可能就不符合要求 for(int k = 0; k < 4; k++) { int a = x + dx[k], b = y + dy[k]; if(check(a, b, step)) { if(st[a][b] == 2) return step; if(!st[a][b]) { st[a][b] = 1; qb.push({a, b}); } } } } } for(int i = 0; i < 1; i++) { for(int j = 0, len = qg.size(); j < len; j++) { auto t = qg.front(); qg.pop(); int x = t.first, y = t.second; if(!check(x, y, step)) continue; for(int k = 0; k < 4; k++) { int a = x + dx[k], b = y + dy[k]; if(check(a, b, step)) { if(st[a][b] == 1) return step; if(!st[a][b]) { st[a][b] = 2; qg.push({a, b}); } } } } } } return -1; } int main() { int T; cin >> T; while(T--) { cin >> n >> m; for(int i = 0; i < n; i++) scanf("%s", g[i]); printf("%d\n", bfs()); } return 0; }