LeetCode 题解工作台
找出最安全路径
给你一个下标从 0 开始、大小为 n x n 的二维矩阵 grid ，其中 (r, c) 表示： 如果 grid[r][c] = 1 ，则表示一个存在小偷的单元格 如果 grid[r][c] = 0 ，则表示一个空单元格 你最开始位于单元格 (0, 0) 。在一步移动中，你可以移动到矩阵中的任一相邻…
6
题型
6
代码语言
3
相关题
当前训练重点
中等 · 二分·搜索·答案·空间
答案摘要
我们可以先找出所有小偷的位置，然后从这些位置开始进行多源 BFS，得到每个位置到小偷的最短距离，然后按照距离从大到小排序，将每个位置逐个加入并查集，如果最终起点和终点在同一个连通分量中，那么当前距离就是答案。 时间复杂度 $O(n^2 \times \log n)$，空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你一个下标从 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 <= 400grid[i].length == ngrid[i][j]为0或1grid至少存在一个小偷
解题思路
方法一：多源 BFS + 排序 + 并查集
我们可以先找出所有小偷的位置，然后从这些位置开始进行多源 BFS，得到每个位置到小偷的最短距离，然后按照距离从大到小排序，将每个位置逐个加入并查集，如果最终起点和终点在同一个连通分量中，那么当前距离就是答案。
时间复杂度 ，空间复杂度 。
class UnionFind:
def __init__(self, n):
self.p = list(range(n))
self.size = [1] * n
def find(self, x):
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, a, b):
pa, pb = self.find(a), self.find(b)
if pa == pb:
return False
if self.size[pa] > self.size[pb]:
self.p[pb] = pa
self.size[pa] += self.size[pb]
else:
self.p[pa] = pb
self.size[pb] += self.size[pa]
return True
class Solution:
def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
n = len(grid)
if grid[0][0] or grid[n - 1][n - 1]:
return 0
q = deque()
dist = [[inf] * n for _ in range(n)]
for i in range(n):
for j in range(n):
if grid[i][j]:
q.append((i, j))
dist[i][j] = 0
dirs = (-1, 0, 1, 0, -1)
while q:
i, j = q.popleft()
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < n and 0 <= y < n and dist[x][y] == inf:
dist[x][y] = dist[i][j] + 1
q.append((x, y))
q = ((dist[i][j], i, j) for i in range(n) for j in range(n))
q = sorted(q, reverse=True)
uf = UnionFind(n * n)
for d, i, j in q:
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < n and 0 <= y < n and dist[x][y] >= d:
uf.union(i * n + j, x * n + y)
if uf.find(0) == uf.find(n * n - 1):
return int(d)
return 0
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n^2 \cdot \log (n)) |
| 空间 | O(n^2) |
面试官常问的追问
外企场景- question_mark
Candidate effectively applies binary search over a range of potential safeness factors.
- question_mark
Candidate demonstrates clear understanding of BFS for pathfinding in a grid with constraints.
- question_mark
Candidate explains the trade-offs in combining binary search and BFS to optimize the solution.
常见陷阱
外企场景- error
Forgetting to account for the thieves in the grid when calculating safeness factor.
- error
Misunderstanding the binary search range, which may lead to incorrect results.
- error
Not efficiently handling the BFS queue, leading to performance issues for larger grids.
进阶变体
外企场景- arrow_right_alt
Handling grids with varying thief positions and grid sizes.
- arrow_right_alt
Modifying the problem to account for multiple thieves instead of a single thief.
- arrow_right_alt
Changing the grid shape, such as making it non-square, and adjusting the approach.