算法题 算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持因为它具有很高的价值算法就是这样✨ 作者简介硕风和炜CSDN-Java领域优质创作者保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 恭喜你发现一枚宝藏博主,赶快收入囊中吧 人生如棋我愿为卒行动虽慢可谁曾见我后退一步 算法题 目录 题目链接⛲ 题目描述 求解思路实现代码运行结果⚡ 滑动窗口 二分答案 多源 BFS原题题意安全系数定义边界限制 核心逻辑拆解模块 1多源 BFS 预处理每个格子到最近小偷的最短距离模块 2二分答案寻找最大安全系数整体思路总结 实现代码 关键原理说明多源 BFS 原理二分答案原理BFS 连通校验原理为什么不能暴力 DFS 枚举所有路径 运行效率时间复杂度空间复杂度 共勉 题目链接2812. 找出最安全路径⛲ 题目描述给你一个下标从 0 开始、大小为 n x n 的二维矩阵 grid 其中 (r, c) 表示如果 grid[r][c] 1 则表示一个存在小偷的单元格如果 grid[r][c] 0 则表示一个空单元格你最开始位于单元格 (0, 0) 。在一步移动中你可以移动到矩阵中的任一相邻单元格包括存在小偷的单元格。矩阵中路径的 安全系数 定义为从路径中任一单元格到矩阵中任一小偷所在单元格的 最小 曼哈顿距离。返回所有通向单元格 (n - 1, n - 1) 的路径中的 最大安全系数 。单元格 (r, c) 的某个 相邻 单元格是指在矩阵中存在的 (r, c 1)、(r, c - 1)、(r 1, c) 和 (r - 1, c) 之一。两个单元格 (a, b) 和 (x, y) 之间的 曼哈顿距离 等于 | a - x | | b - y | 其中 |val| 表示 val 的绝对值。示例 1输入grid [[1,0,0],[0,0,0],[0,0,1]]输出0解释从 (0, 0) 到 (n - 1, n - 1) 的每条路径都经过存在小偷的单元格 (0, 0) 和 (n - 1, n - 1) 。示例 2输入grid [[0,0,1],[0,0,0],[0,0,0]]输出2解释上图所示路径的安全系数为 2该路径上距离小偷所在单元格02最近的单元格是00。它们之间的曼哈顿距离为 | 0 - 0 | | 0 - 2 | 2 。可以证明不存在安全系数更高的其他路径。示例 3输入grid [[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]]输出2解释上图所示路径的安全系数为 2该路径上距离小偷所在单元格03最近的单元格是12。它们之间的曼哈顿距离为 | 0 - 1 | | 3 - 2 | 2 。该路径上距离小偷所在单元格30最近的单元格是32。它们之间的曼哈顿距离为 | 3 - 3 | | 0 - 2 | 2 。可以证明不存在安全系数更高的其他路径。提示1 grid.length n 400grid[i].length ngrid[i][j] 为 0 或 1grid 至少存在一个小偷 求解思路实现代码运行结果⚡ 滑动窗口 二分答案 多源 BFS原题题意给定一个 n × n 的二维网格 gridgrid[i][j] 1该位置存在小偷grid[i][j] 0空白可通行格子需要寻找一条从左上角 (0,0) 到右下角 (n-1,n-1) 的路径仅能上下左右移动。安全系数定义安全系数定义一条路径的安全系数 路径中所有格子到最近小偷距离的最小值。目标求出所有可行路径中最大的安全系数。边界限制网格尺寸 1 ≤ n ≤ 400起点 / 终点若本身是小偷直接返回 0。 核心逻辑拆解整体分为两大模块多源 BFS 预处理距离矩阵 二分答案 BFS 校验可行性模块 1多源 BFS 预处理每个格子到最近小偷的最短距离所有小偷作为同步起点全部入队逐层向外扩散每个格子第一次被访问时记录距离该值就是到最近小偷的曼哈顿最短距离生成dist[i][j] 矩阵后续直接取用无需重复计算距离。模块 2二分答案寻找最大安全系数二分范围安全系数最小为 0最大为 2n网格对角线极限距离二分中点 mid 代表我们猜测的安全下限能否存在一条起点到终点的路径路径上每一格 dist[i][j] ≥ mid校验逻辑BFS 连通性起点距离小于 mid 直接不合法只走距离≥mid 的格子看能否连通终点校验成功说明存在更优解左边界右移记录当前答案校验失败安全值过大右边界左移二分结束后保存的最大值即为最终结果。整体思路总结先用多源 BFS 一次性算出全网格最短安全距离再用二分快速缩小目标值搭配 BFS 做连通性判断规避暴力 DFS 枚举所有路径的指数级超时问题。 实现代码classSolution{int[][]dirs{{-1,0},{1,0},{0,-1},{0,1}};intn;int[][]dist;publicintmaximumSafenessFactor(ListListIntegergrid){ngrid.size();distnewint[n][n];for(int[]row:dist)Arrays.fill(row,-1);Queueint[]qnewLinkedList();// 多源BFS初始化所有小偷入队for(inti0;in;i){for(intj0;jn;j){if(grid.get(i).get(j)1){dist[i][j]0;q.offer(newint[]{i,j});}}}// 多源BFS计算每个格子到最近小偷最短距离while(!q.isEmpty()){int[]curq.poll();intxcur[0],ycur[1];for(int[]d:dirs){intnxxd[0],nyyd[1];if(nx0nxnny0nyndist[nx][ny]-1){dist[nx][ny]dist[x][y]1;q.offer(newint[]{nx,ny});}}}// 二分安全系数intl0,rnn;intans0;while(lr){intmidl(r-l)/2;if(check(mid)){ansmid;lmid1;}else{rmid-1;}}returnans;}// 判断是否存在路径所有格子dist limitbooleancheck(intlimit){if(dist[0][0]limit)returnfalse;boolean[][]visnewboolean[n][n];Queueint[]qnewLinkedList();q.offer(newint[]{0,0});vis[0][0]true;while(!q.isEmpty()){int[]curq.poll();intxcur[0],ycur[1];if(xn-1yn-1)returntrue;for(int[]d:dirs){intnxxd[0],nyyd[1];if(nx0nxnny0nyn!vis[nx][ny]dist[nx][ny]limit){vis[nx][ny]true;q.offer(newint[]{nx,ny});}}}returnfalse;}publicintgetDistance(inta,intb,intx,inty){returnMath.abs(a-x)Math.abs(b-y);}} 关键原理说明多源 BFS 原理普通单源 BFS 只有一个起点逐层扩散多源 BFS 将所有小偷作为初始起点同时入队同步向外逐层遍历。每个格子第一次被队列访问时必然来自距离它最近的小偷直接赋值距离一次遍历完成全网格最短距离计算。对比暴力遍历所有小偷求曼哈顿距离时间复杂度大幅降低。二分答案原理题目求 “路径最小值的最大值”是典型二分答案题型安全系数存在单调性若安全值 k 可行则所有小于 k 的值一定可行若 k 不可行所有大于 k 的值均不可行利用单调性二分快速锁定最大合法值避免暴力枚举所有安全系数。BFS 连通校验原理二分得到目标安全下限后只需判断网格中是否存在连通起点终点的通路且通路所有格子距离小偷都不低于该下限。BFS适合网格连通性判断不会出现 DFS 递归深度溢出问题。为什么不能暴力 DFS 枚举所有路径网格最大 400×400路径数量呈指数级增长暴力回溯 DFS 会直接超时无法通过中等规模测试用例。 运行效率时间复杂度多源 BFS 预处理(O(n^2))每个格子仅入队、出队一次二分循环二分区间最大为 2n循环次数 (O(logn))每次二分内 BFS 校验(O(n^2))总复杂度(O(n^2 * logn))空间复杂度(O(n^2))用于存储距离矩阵、访问标记数组、BFS 队列400×400 网格内存占用可控无栈溢出风险。 共勉最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉