【LeetCode: 2812. 找出最安全路径 + 二分答案 + 多源 BFS】

硕风和炜

276人浏览 · 2026-07-01 20:45:27

硕风和炜 · 2026-07-01 20:45:27 发布

在这里插入图片描述

🚀 算法题 🚀

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨
🌲 作者简介：硕风和炜，CSDN-Java领域优质创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯

🚀 算法题 🚀

在这里插入图片描述

🍔 目录

🚩 题目链接

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：

该路径上距离小偷所在单元格（0，2）最近的单元格是（0，0）。它们之间的曼哈顿距离为 | 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：

该路径上距离小偷所在单元格（0，3）最近的单元格是（1，2）。它们之间的曼哈顿距离为 | 0 - 1 | + | 3 - 2 | = 2 。

该路径上距离小偷所在单元格（3，0）最近的单元格是（3，2）。它们之间的曼哈顿距离为 | 3 - 3 | + | 0 - 2 | = 2 。
可以证明，不存在安全系数更高的其他路径。

提示：

1 <= grid.length == n <= 400
grid[i].length == n
grid[i][j] 为 0 或 1
grid 至少存在一个小偷

🌟 求解思路&实现代码&运行结果

🥦 二分答案 + 多源 BFS

原题题意

给定一个 n × n 的二维网格 grid：

grid[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 枚举所有路径的指数级超时问题。

🥦 实现代码

class Solution {
    int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
    int n;
    int[][] dist;

    public int maximumSafenessFactor(List<List<Integer>> grid) {
        n = grid.size();
        dist = new int[n][n];
        for(int[] row : dist) Arrays.fill(row, -1);
        Queue<int[]> q = new LinkedList<>();

        // 多源BFS初始化：所有小偷入队
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(grid.get(i).get(j) == 1){
                    dist[i][j] = 0;
                    q.offer(new int[]{i, j});
                }
            }
        }

        // 多源BFS计算每个格子到最近小偷最短距离
        while(!q.isEmpty()){
            int[] cur = q.poll();
            int x = cur[0], y = cur[1];
            for(int[] d : dirs){
                int nx = x + d[0], ny = y + d[1];
                if(nx >=0 && nx < n && ny >=0 && ny < n && dist[nx][ny] == -1){
                    dist[nx][ny] = dist[x][y] + 1;
                    q.offer(new int[]{nx, ny});
                }
            }
        }

        // 二分安全系数
        int l = 0, r = n + n;
        int ans = 0;
        while(l <= r){
            int mid = l + (r - l) / 2;
            if(check(mid)){
                ans = mid;
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        return ans;
    }

    // 判断是否存在路径，所有格子dist >= limit
    boolean check(int limit){
        if(dist[0][0] < limit) return false;
        boolean[][] vis = new boolean[n][n];
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{0, 0});
        vis[0][0] = true;

        while(!q.isEmpty()){
            int[] cur = q.poll();
            int x = cur[0], y = cur[1];
            if(x == n-1 && y == n-1) return true;
            for(int[] d : dirs){
                int nx = x + d[0], ny = y + d[1];
                if(nx >=0 && nx < n && ny >=0 && ny < n && !vis[nx][ny] && dist[nx][ny] >= limit){
                    vis[nx][ny] = true;
                    q.offer(new int[]{nx, ny});
                }
            }
        }
        return false;
    }

    public int getDistance(int a, int b, int x, int y) {
        return Math.abs(a - x) + Math.abs(b - y);
    }
}