BFS 三题题解复盘前言本次三题覆盖了 BFS 的三大核心模型题目模型核心特征P1747 好奇怪的游戏反向 BFS从终点反向搜索移动可逆P1443 马的遍历距离 BFS单源多点距离数组P2895 流星雨时间限制 BFS预处理危险时间 BFS第一部分P1747 好奇怪的游戏基本信息项目内容题目编号、来源P1747 洛谷 / 好奇怪的游戏训练层级B BFS基础知识版块BFS、反向搜索、状态搜索解题前・关键信号识别维度分析目标、约束、底层结构目标两匹马到达 (1,1) 的最少步数约束移动规则固定日字田字底层结构棋盘可看作无权图每个位置是一个节点移动方式是边。数据规模坐标范围小BFS 完全可行。候选算法和依据BFS依据求最少步数 无权图最短路。复杂度预判时间复杂度 O(棋盘面积 × 移动方式数)空间复杂度 O(棋盘面积)。解题后・外化复盘维度内容实现结构 / 核心思路第一步从终点 (1,1) 开始 BFS反向搜索因为马的移动可逆从终点搜索得到所有位置到终点的距离第二步枚举 12 种移动方式8 个日字 4 个田字未访问位置入队第三步输出 dis[x][y] 即为该点到 (1,1) 的最少步数。核心思想移动对称性 → 反向 BFS 一次预处理多次查询 O(1)。错因回溯1. 忘记调用 BFS 就直接输出 dis 数组2. 方向数组写错日字 8 个 田字 4 个共 12 种3. BFS 入队时忘记立即标记访问。边界和易错点1. 坐标从 1 开始不能小于 12. 移动方式共 12 种不是 8 种3. BFS 入队时立即标记防止重复入队。下次看到什么信号我应该想到这个方法看到「最少步数 棋盘移动规则固定」用 BFS 最短路看到「多组询问到同一点」用反向 BFS 预处理。AC 完整代码#includeiostream#includecstring#includequeue#includealgorithmusingnamespacestd;intx1,y1,x2,y2;intdis[25][25];intdx[]{2,1,-1,-2,-2,-1,1,2,2,2,-2,-2};intdy[]{1,2,2,1,-1,-2,-2,-1,2,-2,2,-2};voidbfs(){queuepairint,intq;q.push({1,1});memset(dis,-1,sizeof(dis));dis[1][1]0;while(!q.empty()){auto[x,y]q.front();q.pop();for(inti0;i12;i){intnxxdx[i];intnyydy[i];if(nx0ny0dis[nx][ny]-1){dis[nx][ny]dis[x][y]1;q.push({nx,ny});}}}}intmain(){cinx1y1x2y2;bfs();coutdis[x1][y1]endl;coutdis[x2][y2]endl;return0;}第二部分P1443 马的遍历基本信息项目内容题目编号、来源P1443 洛谷 / 马的遍历训练层级B BFS基础强化知识版块BFS、距离数组、网格搜索解题前・关键信号识别维度分析目标、约束、底层结构目标求一个马到棋盘所有点的最短距离约束棋盘 n×mn,m ≤ 400底层结构单源多点 BFS 距离扩散。数据规模n,m ≤ 400400×400160000BFS 完全可行。候选算法和依据BFS依据一个起点到所有点的最短距离 BFS 距离数组。复杂度预判时间复杂度 O(n×m×8)空间复杂度 O(n×m)。解题后・外化复盘维度内容实现结构 / 核心思路第一步从起点 (x,y) 开始 BFS第二步枚举 8 种马走日方式第三步每到一个新格子记录dis[nx][ny] dis[x][y] 1第四步输出整个 dis 矩阵。核心思想BFS 天然具有最短路性质第一次到达即为最短距离。错因回溯1. 输出时循环下标写错从 0 开始而非从 1 开始2. 方向数组只有 8 种马走日3. 距离数组初始化为 0 导致无法区分未访问和起点。边界和易错点1. 棋盘坐标从 1 开始输出时循环for(int i1;in;i)2. 距离数组初始化为 -13. 入队时立即标记距离。下次看到什么信号我应该想到这个方法看到「一个起点 求所有点最短距离」用 BFS 距离扩散。AC 完整代码#includeiostream#includecstring#includequeue#includealgorithmusingnamespacestd;intn,m,x,y;intdis[405][405];intdx[]{2,2,-2,-2,1,1,-1,-1};intdy[]{1,-1,1,-1,2,-2,2,-2};voidbfs(inti,intj){queuepairint,intq;memset(dis,-1,sizeof(dis));q.push({i,j});dis[i][j]0;while(!q.empty()){auto[x,y]q.front();q.pop();for(inta0;a8;a){intnxxdx[a];intnyydy[a];if(nx0nxnny0nymdis[nx][ny]-1){dis[nx][ny]dis[x][y]1;q.push({nx,ny});}}}}intmain(){cinnmxy;bfs(x,y);for(inti1;in;i){for(intj1;jm;j){coutdis[i][j] ;}coutendl;}return0;}第三部分P2895 流星雨时间限制 BFS基本信息项目内容题目编号、来源P2895 洛谷 / Meteor Shower训练层级B BFS进阶知识版块BFS、预处理、时间状态解题前・关键信号识别维度分析目标、约束、底层结构目标找到最快到达安全位置的时间约束格子会在某个时间被摧毁底层结构状态 位置 时间需要预处理危险时间。数据规模坐标 ≤ 300影响范围可能到 301搜索范围扩展到 505。候选算法和依据预处理 BFS依据每个位置有开放/关闭时间BFS 时需判断到达时间是否早于危险时间。复杂度预判时间复杂度 O(棋盘面积)空间复杂度 O(棋盘面积)。解题后・外化复盘维度内容实现结构 / 核心思路第一步定义dis[x][y]表示该格子最早被摧毁的时间初始化为 INF第二步读入流星数据更新自身及上下左右四个格子共 5 个点的危险时间取最小值第三步 BFS 从 (0,0) 开始vis[x][y]记录到达时间第四步转移条件vis[x][y] 1 dis[nx][ny]第五步若到达dis[x][y] INF的位置即为安全点输出时间。核心思想预处理危险时间BFS 带时间状态搜索。错因回溯1. 使用 set 记录危险位置无法记录具体时间 → 必须用时间数组2. 危险时间数组未初始化为 INF默认 0 导致错误3. 边界范围不足流星坐标 ≤300影响可能到 3014. 到达时间必须严格小于摧毁时间不是。边界和易错点1. 起点 (0,0) 可能在 t0 时被摧毁需特判2. 流星影响 5 个格子自身 上下左右3. 搜索范围扩展到 5054. BFS 距离即为时间5. 入队时立即标记访问。下次看到什么信号我应该想到这个方法看到「最短路 每个位置有开放/关闭时间」用时间限制 BFS。AC 完整代码#includeiostream#includecstring#includequeue#includealgorithm#includesetusingnamespacestd;setpairint,ints;intvis[505][505];intdis[505][505];intdx[]{-1,0,1,0,0};intdy[]{0,1,0,-1,0};constintINF0x3f3f3f3f;intbfs(){if(dis[0][0]0){return-1;}memset(vis,-1,sizeof(vis));queuepairint,intq;q.push({0,0});vis[0][0]0;while(!q.empty()){auto[x,y]q.front();q.pop();if(dis[x][y]INF){returnvis[x][y];}for(inti0;i4;i){intnxxdx[i];intnyydy[i];if(nx0||ny0||nx505||ny505)continue;if(vis[nx][ny]!-1)continue;if(vis[x][y]1dis[nx][ny])continue;vis[nx][ny]vis[x][y]1;q.push({nx,ny});}}return-1;}intmain(){memset(dis,0x3f,sizeof(dis));intm;cinm;while(m--){intx,y,t;cinxyt;for(inti0;i5;i){intnxxdx[i];intnyydy[i];if(nx0ny0nx505ny505){s.insert({nx,ny});if(dis[nx][ny]t){dis[nx][ny]t;}}}}coutbfs();return0;}
