找出最安全路径

标签: 广度优先搜索并查集数组二分查找矩阵

难度: Medium

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

Submission

运行时间: 1184 ms

内存: 27.2 MB

class Solution:
    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
        if grid[0][0] or grid[-1][-1]: return 0
        from sortedcontainers import SortedSet
        n = len(grid)
        q = deque((r, c) for r, row in enumerate(grid) for c, v in enumerate(row) if v)
        while q:
            r, c = q.popleft()
            dist = grid[r][c] + 1
            for nr, nc in [(r, c-1), (r, c+1), (r-1, c), (r+1, c)]:
                if nr < 0 or nr == n or nc < 0 or nc == n or grid[nr][nc]:
                    continue
                grid[nr][nc] = dist
                q.append((nr, nc))
        res = min(grid[0][0], grid[-1][-1])
        q = deque([(0, 0)])
        visited = [[0]*n for _ in range(n)]
        visited[0][0] = 1
        candidates = SortedSet()
        while q:
            while q:
                r, c = q.popleft()
                if r == n - 1 and c == n - 1: return res - 1
                for nr, nc in [(r, c-1), (r, c+1), (r-1, c), (r+1, c)]:
                    if nr < 0 or nr == n or nc < 0 or nc == n or visited[nr][nc]:
                        continue
                    if grid[nr][nc] < res:
                        candidates.add((grid[nr][nc], nr, nc))
                    else:
                        visited[nr][nc] = 1
                        q.append((nr, nc))
            res = candidates[-1][0]
            off = candidates.bisect_left((res, 0, 0))
            for _, r, c in candidates[off:]:
                q.append((r, c))
                visited[r][c] = 1
            del candidates[off:]

Explain

题解采用了两阶段的广度优先搜索（BFS）策略来求解最大的安全系数。首先，从所有小偷所在的位置开始，对整个网格执行BFS以计算出每个单元格到最近小偷的距离。然后，使用另一轮BFS来找到从起点(0,0)到终点(n-1,n-1)的路径，同时尽可能保持路径上单元格到最近小偷的最小曼哈顿距离最大。这通过追踪当前路径中最小距离的最大值来实现。如果起点或终点有小偷，安全系数直接为0。第一轮BFS结束后，会确定到达每个单元格的最小距离。在第二轮BFS中，会检查从当前单元格到邻近单元格是否能保持或增加这个最小距离的最大值，并优先扩展那些能维持最大距离的路径。

时间复杂度: O(n^2 log n)

空间复杂度: O(n^2)

class Solution:
    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
        # 特殊情况：起点或终点有小偷
        if grid[0][0] or grid[-1][-1]: return 0
        from sortedcontainers import SortedSet
        n = len(grid)
        q = deque((r, c) for r, row in enumerate(grid) for c, v in enumerate(row) if v)
        # 第一轮BFS，计算到最近小偷的距离
        while q:
            r, c = q.popleft()
            dist = grid[r][c] + 1
            for nr, nc in [(r, c-1), (r, c+1), (r-1, c), (r+1, c)]:
                if nr < 0 or nr == n or nc < 0 or nc == n or grid[nr][nc]:
                    continue
                grid[nr][nc] = dist
                q.append((nr, nc))
        res = min(grid[0][0], grid[-1][-1])
        q = deque([(0, 0)])
        visited = [[0]*n for _ in range(n)]
        visited[0][0] = 1
        candidates = SortedSet()
        # 第二轮BFS，尝试保持最大的最小距离
        while q:
            while q:
                r, c = q.popleft()
                if r == n - 1 and c == n - 1: return res - 1
                for nr, nc in [(r, c-1), (r, c+1), (r-1, c), (r+1, c)]:
                    if nr < 0 or nr == n or nc < 0 or nc == n or visited[nr][nc]:
                        continue
                    if grid[nr][nc] < res:
                        candidates.add((grid[nr][nc], nr, nc))
                    else:
                        visited[nr][nc] = 1
                        q.append((nr, nc))
            res = candidates[-1][0]
            off = candidates.bisect_left((res, 0, 0))
            for _, r, c in candidates[off:]:
                q.append((r, c))
                visited[r][c] = 1
            del candidates[off:]

Explore

在大矩阵中，第一轮BFS确实可能导致性能问题，因为它必须访问矩阵中的每个单元格来更新距离。这个过程的时间复杂度是O(n^2)，其中n是网格的维度。更高效的方法可能包括使用多线程或并行处理来加速BFS过程，或者在某些情况下使用启发式算法如A*寻找最近小偷的路径，尽管这后者可能需要特定条件下的优化。

是的，我们可以在算法的最开始就检查起点和终点是否有小偷。如果有，直接返回安全系数为0，这样可以避免不必要的计算，从而优化整体算法的效率。这种早期终止的策略通常在算法设计中被用来处理特殊情况，以减少资源消耗。

优先扩展能维持最大距离的路径是一种启发式方法，它旨在最大化安全系数，但不一定能保证找到最短的路径或其他类型的最优路径。在某些情况下，可能存在多条路径都能达到相同的最大安全系数，但长度不同。因此，这种策略确实可能导致在路径长度或其他因素上不是最优的情况。

在第二轮BFS中，应该考虑第一轮BFS设置的距离值，因为这些值代表了到最近小偷的最小曼哈顿距离。如果第二轮BFS中不正确地处理这些值，可能会导致无法正确评估路径的安全系数。因此，确实需要明确地检查和利用这些距离值来保证第二轮BFS的准确性和有效性。