一、题目介绍题目名称题目大意你和若干只怪物处于一个迷宫中。每经过一秒你可以向上、下、左、右移动一格每只怪物也可以同时向上、下、左、右移动一格墙壁无法通过。你的目标是从起点A出发到达迷宫边界上的任意一个格子并且在整个移动过程中都不能和怪物处于同一个格子。即使怪物提前知道你的完整逃跑路线你的路线也必须保证安全。二、输入格式第一行输入两个整数n m表示迷宫有n行、m列。接下来输入n行字符串每行包含m个字符#墙壁不能通过.空地可以通过A人物起点M怪物起点。地图中恰好存在一个A但可能存在多个怪物。三、输出格式如果不存在安全逃生路线输出NO如果存在安全逃生路线输出YES 路径长度 路径字符串路径字符串中的字符含义如下U向上移动D向下移动L向左移动R向右移动。四、问题分析这道题不能只从人物起点进行一次普通 BFS。原因是人物可以到达某个位置并不代表人物能够安全到达这个位置。例如人物和怪物到达某个格子的时间分别为人物3 秒 怪物3 秒虽然人物可以走到这个格子但怪物也会同时到达因此这条路线是不安全的。人物进入某个格子的必要条件是人物到达时间 怪物最早到达时间注意这里必须是严格小于不能是小于等于。因此我们需要分别计算怪物最早什么时候到达每个格子人物在保证比怪物先到的情况下能否到达边界。五、总体解题思路整道题需要进行两次 BFS第一次 BFS从所有怪物同时出发 计算怪物到达每个格子的最早时间 第二次 BFS从人物 A 出发 只进入人物能比怪物更早到达的格子如果人物能够到达边界则说明存在逃生路线。六、第一次 BFS计算怪物最早到达时间1. 为什么是多源 BFS地图中可能存在多个怪物。例如M.....M ....... ...A...对于任意一个格子我们关心的是所有怪物中最早到达这个格子的怪物需要多少时间。如果分别从每个怪物执行一次 BFS时间复杂度会非常高。正确做法是一开始把所有怪物都加入同一个队列然后执行一次 BFS。初始化if (mp[i][j] M) { monsterTime[i][j] 0; q.push({i, j}); }所有怪物都作为距离为0的起点。之后执行普通 BFS就能得到所有格子距离最近怪物的最短距离。2. 怪物时间数组定义int monsterTime[1005][1005];其中monsterTime[x][y]表示怪物最早到达格子(x,y)所需的时间。初始化为一个很大的数monsterTime[i][j] INF;表示当前没有怪物能够到达该位置。如果某个格子本身就是怪物monsterTime[i][j] 0;3. 怪物 BFS 转移对于当前格子(x,y)枚举四个方向int nx x dx[i]; int ny y dy[i];如果新格子没有越界不是墙没有被怪物访问过那么进行更新monsterTime[nx][ny] monsterTime[x][y] 1; q.push({nx, ny});由于 BFS 按照距离从小到大扩展因此第一次访问某个格子时得到的就是怪物最早到达时间。七、第二次 BFS人物寻找安全路线计算完怪物时间之后从人物起点A再执行一次 BFS。定义int personTime[1005][1005];其中personTime[x][y]表示人物到达(x,y)所需要的最少时间。初始化为personTime[i][j] -1;-1表示人物还没有访问该位置。人物起点时间为personTime[startX][startY] 0;1. 人物什么时候能进入下一个格子假设人物当前位于(x,y)当前到达时间是personTime[x][y]那么进入相邻格子(nx,ny)的时间是int newTime personTime[x][y] 1;人物可以进入这个格子需要满足newTime monsterTime[nx][ny]也就是if (newTime monsterTime[nx][ny]) { continue; }这里有两种不安全情况。情况一怪物先到人物到达时间5 怪物到达时间3人物进入时怪物早已到达该位置。情况二同时到达人物到达时间5 怪物到达时间5人物和怪物会在同一时刻进入同一个位置同样不安全。因此只有人物时间 怪物时间才是安全的。八、如何判断逃生成功题目要求人物到达任意一个边界格子。对于坐标(x,y)如果满足下面任意一个条件它就是边界x 1 x n y 1 y m因此在人物 BFS 中每次从队列取出一个位置后可以判断if (x 1 || x n || y 1 || y m) { endpoint {x, y}; break; }由于 BFS 是按照最短距离搜索所以第一次到达边界时得到的就是一条最短安全路径。九、路径记录与还原只判断能否到达边界还不够题目还要求输出具体路径。因此人物 BFS 时要记录人物是通过哪个方向进入每个格子的。定义char pre[1005][1005];例如pre[nx][ny] D;表示人物是从上面的格子向下移动进入(nx,ny)的。1. 方向数组可以将坐标变化和方向字符对应起来int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1}; char direction[4] {D, U, R, L};对应关系如下下标dxdy方向010D1-10U201R30-1L人物从(x,y)走到(nx,ny)时记录pre[nx][ny] direction[i];2. 从终点反向回到起点找到终点后从终点开始向起点倒推。假设pre[x][y] D;表示人物之前是向下走到当前格子的上一个格子 | D ↓ 当前格子因此倒推时应该向上返回x--;完整对应关系如下记录的移动方向倒推时的坐标变化Dx--UxRy--Ly代码如下while (x ! start.first || y ! start.second) { char dir pre[x][y]; path.push_back(dir); if (dir D) { x--; } else if (dir U) { x; } else if (dir R) { y--; } else if (dir L) { y; } }此时得到的路径顺序是终点 → 起点所以最后需要反转reverse(path.begin(), path.end());十、特殊情况1. 人物起点本身就在边界例如A... ####人物一开始就位于边界不需要移动。此时应该输出YES 0人物 BFS 第一次取出起点时就会判断它是边界因此路径长度为0。2. 地图中没有怪物如果地图中不存在怪物那么所有格子的怪物时间都是INFmonsterTime[i][j] INF;人物移动时newTime INF一定成立因此人物可以像普通迷宫 BFS 一样寻找出口。3. 怪物无法到达某个区域如果怪物被墙隔开无法到达某个格子那么该位置的monsterTime[x][y] INF人物可以安全进入这个区域。十一、涉及的知识点1. 广度优先搜索 BFSBFS 适用于无权图中的最短路问题。迷宫中每次移动的代价都是1因此可以使用 BFS 计算最少移动次数。BFS 的核心数据结构是队列queuepairint,int q;2. 多源 BFS普通 BFS 只有一个起点多源 BFS 有多个起点。多源 BFS 的初始化方式是for (所有起点) { dist[x][y] 0; q.push({x, y}); }然后按照普通 BFS 进行扩展。这道题中所有怪物都是 BFS 的起点。常见多源 BFS 应用包括计算每个位置到最近怪物的距离计算每个位置到最近医院的距离火焰扩散问题洪水扩散问题腐烂橘子问题多个传染源同时扩散。3. BFS 路径还原BFS 不仅可以求最短距离还可以记录搜索路径。常见的路径记录方式有两种。方法一记录父节点坐标parentX[nx][ny] x; parentY[nx][ny] y;方法二记录移动方向pre[nx][ny] direction[i];本题使用第二种方法空间更少也更方便输出方向字符串。4. 时间模型本题本质上是一个“动态障碍物”问题。怪物会随着时间不断移动因此某个格子是否安全不仅与位置有关还与到达时间有关。安全条件为人物到达时间 危险到达时间这种思想也常用于火灾逃生洪水逃生病毒扩散毒气扩散敌人追击动态迷宫。十二、正确性说明可以从两个方面说明算法正确性。1. 怪物时间的正确性所有怪物一开始都以距离0加入队列。BFS 按照距离从小到大的顺序访问格子因此每个格子第一次被访问时对应的就是所有怪物中最快到达该格子的时间。所以monsterTime[x][y]正确表示怪物到达(x,y)的最早时间。2. 人物路径的安全性人物只有在满足以下条件时才会进入新格子newTime monsterTime[nx][ny]因此人物进入过的每个格子都保证人物严格早于任何怪物到达。所以人物搜索到的路径不会和怪物同时处于同一个格子。当人物到达边界时就得到一条合法的逃生路线。十四、复杂度分析地图共有n × m个格子。怪物 BFS 中每个格子最多访问一次O(nm)人物 BFS 中每个格子最多访问一次O(nm)路径还原最多经过nm个格子O(nm)因此总时间复杂度为O(nm)空间复杂度为O(nm)题目中n,m ≤ 1000最多有约一百万个格子可以通过。十五、完整源码#include bits/stdc.h using namespace std; const int N 1005; const int INF 1e9; int n, m; // 地图 char mp[N][N]; // 怪物到达每个位置的最早时间 int monsterTime[N][N]; // 人物到达每个位置的最早时间 int personTime[N][N]; // 记录人物通过哪个方向到达当前位置 char pre[N][N]; // 人物起点 pairint, int startPoint; // 四个方向下、上、右、左 int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1}; char direction[4] {D, U, R, L}; /** * 判断坐标是否在地图范围内 */ bool isInside(int x, int y) { return x 1 x n y 1 y m; } /** * 判断当前位置是否为边界 */ bool isBoundary(int x, int y) { return x 1 || x n || y 1 || y m; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; queuepairint, int monsterQueue; /* 读入地图同时初始化距离数组。 所有怪物都加入队列作为多源 BFS 的起点。 */ for (int i 1; i n; i) { for (int j 1; j m; j) { cin mp[i][j]; monsterTime[i][j] INF; personTime[i][j] -1; if (mp[i][j] M) { monsterTime[i][j] 0; monsterQueue.push({i, j}); } if (mp[i][j] A) { startPoint {i, j}; } } } /* 第一次 BFS 从所有怪物同时出发计算怪物到达每个格子的最早时间。 */ while (!monsterQueue.empty()) { auto [x, y] monsterQueue.front(); monsterQueue.pop(); for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; // 越界 if (!isInside(nx, ny)) { continue; } // 墙壁不能通过 if (mp[nx][ny] #) { continue; } // 已经被怪物访问过 if (monsterTime[nx][ny] ! INF) { continue; } monsterTime[nx][ny] monsterTime[x][y] 1; monsterQueue.push({nx, ny}); } } /* 第二次 BFS 从人物起点出发寻找安全的逃生路线。 */ queuepairint, int personQueue; personTime[startPoint.first][startPoint.second] 0; personQueue.push(startPoint); // 记录逃生终点 pairint, int endPoint {-1, -1}; while (!personQueue.empty()) { auto [x, y] personQueue.front(); personQueue.pop(); /* 到达边界说明逃生成功。 在出队时判断可以正确处理人物一开始就在边界的情况。 */ if (isBoundary(x, y)) { endPoint {x, y}; break; } for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; // 越界 if (!isInside(nx, ny)) { continue; } // 墙壁不能通过 if (mp[nx][ny] #) { continue; } // 人物已经访问过 if (personTime[nx][ny] ! -1) { continue; } // 人物到达下一个格子的时间 int newTime personTime[x][y] 1; /* 人物必须严格比怪物更早到达。 如果 newTime monsterTime[nx][ny] 人物会和怪物同时到达也是不安全的。 */ if (newTime monsterTime[nx][ny]) { continue; } personTime[nx][ny] newTime; // 记录人物走到当前位置时使用的方向 pre[nx][ny] direction[i]; personQueue.push({nx, ny}); } } // 没有找到任何边界位置 if (endPoint.first -1) { cout NO\n; return 0; } /* 从终点倒推到起点还原路径。 */ string path; int x endPoint.first; int y endPoint.second; while (x ! startPoint.first || y ! startPoint.second) { char dir pre[x][y]; path.push_back(dir); /* 根据进入当前格子的方向返回上一个格子。 */ if (dir D) { x--; } else if (dir U) { x; } else if (dir R) { y--; } else if (dir L) { y; } } // 当前路径为终点到起点需要反转 reverse(path.begin(), path.end()); cout YES\n; cout path.size() \n; cout path \n; return 0; }十六、总结这道题的关键不是单纯寻找一条从A到边界的路径而是寻找一条在时间上也安全的路径。核心步骤可以概括为1. 将所有怪物加入队列执行多源 BFS 2. 计算怪物到达每个格子的最早时间 3. 从人物起点执行第二次 BFS 4. 只允许人物进入比怪物更早到达的格子 5. 到达边界后通过方向数组还原路径。最重要的判断条件是personTime 1 monsterTime这类“危险不断扩散人物需要逃生”的问题通常都可以使用多源 BFS 预处理危险时间 人物 BFS 寻找安全路径来解决。