2812.找出最安全路径：两次BFS(先进先出队列+优先队列)

【LetMeFly】2812.找出最安全路径：两次BFS(先进先出队列+优先队列)

力扣题目链接：https://leetcode.cn/problems/find-the-safest-path-in-a-grid/

给你一个下标从 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 至少存在一个小偷

解题方法：两次广度优先搜索

初始时候我们只知道哪里有小偷，但不知道每个单元格的安全系数。我们可以通过一次广度优先搜索得到每个单元格的安全系数：

使用一个先入先出队列，初始时将所有小偷单元格入队，接着在队列非空时不断出队。

对于出队的单元格，若其上下左右四个相邻单元格还没有入队过，则入队，并更新相邻单元格的安全系数为当前出队单元格的$安全系数+1$。

队列为空则说明已经求得所有单元格的安全系数

知道了每个单元格的安全系数，剩下的就是求从起点(左上角)到终点(右下角)的尽可能走大安全系数的路径中的最小单元格是多少：

由于路径可以上下左右到出走，所以我们不能简单地DP遍历。一旦在到达终点前我们不得不走了某小安全系数的单元格，那么以后大于等于这个最小安全系数的单元格就能肆无忌惮地走了。

因此可以使用一个优先队列再从起点开始进行一次广度优先搜索，每次出队时更新答案(所经过单元格的最小值)，若出队单元格是终点则直接返回。否则上下左右四个相邻单元格中未遍历过的单元格入队，并按安全系数大的优先为依据优先出队。

  • 时间复杂度$O(n^2\log n)$，因为$O(\log n^2)=O(2\log n)=O(\log n)$
  • 空间复杂度$O(n^2)$

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
/*
 * @LastEditTime: 2026-07-01 22:58:28
 */
#define debug_(x) {cout << #x << ":" << endl; debug(x);}

typedef pair<int, int> pii;
class Solution {
private:
    vector<vector<int>> dis;
    static constexpr int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    void genDis(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<bool>> visited(n, vector<bool>(m, false));
        queue<pii> q;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j]) {
                    q.push({i, j});
                    visited[i][j] = true;
                }
            }
        }

        dis = vector<vector<int>>(n, vector<int>(m));
        while (q.size()) {
            auto [x, y] = q.front();
            q.pop();
            for (int d = 0; d < 4; d++) {
                int nx = x + directions[d][0];
                int ny = y + directions[d][1];
                if (nx >= 0 && nx < n && ny >= 0 && ny <m && !visited[nx][ny]) {
                    q.push({nx, ny});
                    visited[nx][ny] = true;
                    dis[nx][ny] = dis[x][y] + 1;
                }
            }
        }
    }

    int dfs() {
        int n = dis.size(), m = dis[0].size();
        auto cmp = [this](const pii& a, const pii& b) {
            return dis[a.first][a.second] < dis[b.first][b.second];
        };
        priority_queue<pii, vector<pii>, decltype(cmp)> q(cmp);
        vector<vector<bool>> visited(n, vector<bool>(m));
        int ans = min(dis[0][0], dis[n - 1][m - 1]);
        q.push({0, 0});
        visited[0][0] = true;
        if (n == 1 && m == 1) {
            return ans;
        }
        
        while (q.size()) {
            auto [x, y] = q.top();
            q.pop();
            ans = min(ans, dis[x][y]);
            for (int d = 0; d < 4; d++) {
                int nx = x + directions[d][0];
                int ny = y + directions[d][1];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    q.push({nx, ny});
                    if (nx == n - 1 && ny == m - 1) {
                        return ans;
                    }
                }
            }
        }
        return ans;
    }
    
    void debug(vector<vector<int>>& v) {
        int n = v.size(), m = v[0].size();
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                cout << "[[";
            } else {
                cout << " [";
            }

            for (int j = 0; j < m; j++) {
                if (j) {
                    cout << ", ";
                }
                cout << v[i][j];
            }

            if (i == n - 1) {
                cout << "]]";
            } else {
                cout << "],";
            }
            puts("");
        }
    }
public:
    int maximumSafenessFactor(vector<vector<int>>& grid) {
        genDis(grid);
        return dfs();
    }
};

// 忽然发现其实m=n

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
'''
LastEditTime: 2026-07-03 10:59:07
'''
from typing import List
from collections import deque
import heapq

class Solution:
    def __init__(self) -> None:
        self.directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    
    def genDis(self, grid: List[List[int]]):
        n, m = len(grid), len(grid[0])
        dis = [[-1] * m for _ in range(n)]
        q = deque()
        for i, row in enumerate(grid):
            for j, v in enumerate(row):
                if v:
                    q.append((i, j))
                    dis[i][j] = 0
        
        while q:
            x, y = q.popleft()
            for dx, dy in self.directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < m and dis[nx][ny] == -1:
                    q.append((nx, ny))
                    dis[nx][ny] = dis[x][y] + 1
        self.dis = dis

    def dfs(self) -> int:
        n, m = len(self.dis), len(self.dis[0])
        visited = [[False] * m for _ in range(n)]
        pq = [(-self.dis[0][0], 0, 0)]
        visited[0][0] = True
        ans = self.dis[0][0]
        
        while pq:
            dis, x, y = heapq.heappop(pq)
            dis = -dis
            ans = min(ans, dis)
            if x == n - 1 and y == m - 1:
                return ans
            for dx, dy in self.directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
                    visited[nx][ny] = True
                    heapq.heappush(pq, (-self.dis[nx][ny], nx, ny))

    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
        self.genDis(grid)
        return self.dfs()

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源

题解 > LeetCode
#BFS #LeetCode #中等 #二分查找 #堆（优先队列） #并查集 #广度优先搜索 #数组 #矩阵 #题解
2812.找出最安全路径：两次BFS(先进先出队列+优先队列)
https://blog.letmefly.xyz/2026/07/03/LeetCode 2812.找出最安全路径/
作者
发布于
2026年7月3日
许可协议