题目概述
You are given a 0-indexed 2D matrix grid of size n x n, where (r, c) represents:
- A cell containing a thief if
grid[r][c] = 1 - An empty cell if
grid[r][c] = 0
You are initially positioned at cell (0, 0). In one move, you can move to any adjacent cell in the grid, including cells containing thieves.
The safeness factor of a path on the grid is defined as the minimum manhattan distance from any cell in the path to any thief in the grid.
Return the maximum safeness factor of all paths leading to cell (n - 1, n - 1).
An adjacent cell of cell (r, c), is one of the cells (r, c + 1), (r, c - 1), (r + 1, c) and (r - 1, c) if it exists.
The Manhattan distance between two cells (a, b) and (x, y) is equal to |a - x| + |b - y|, where |val| denotes the absolute value of val.
Constraints:
1 <= grid.length == n <= 400grid[i].length == ngrid[i][j]is either0or1.- There is at least one thief in the
grid.
问题分析
首先我们来提炼一下这道题中的要点：
- 存在一个网格，其中每个单元格内包含的数字是 0 或 1 ，分别对应 空单元格 与 盗贼
- 需要进行路径探索，起点为左上角单元格，终点为右下角单元格
- 定义了一个概念为 路径的安全系数 。取这条路径中任意一个单元格，计算其与网格中任意一名盗贼的 曼哈顿距离 ，所得到的所有距离中 最小 的那一个即为路径的安全系数
- 求：所有路径安全系数中 最高 的那一个
思路 & 代码实现
这一章会从最直接的解法开始进行深入的探讨，如果是希望直接阅读正解的朋友请跳转至 此处 。
最直接做法
在不考虑运行效率的情况下，我们可以先写一个不需要太多思考就能实现的简单做法，确保其正确性，随后再进行计算复杂度分析，逐步优化。那么对于这道题来说，我们可以依照问题的定义把它分解一下：
- 找出网格中所有盗贼的位置，并一一记录
- 找出所有从网格左上角出发并在右下角结束的路径，并一一记录
- 对于每一条记录下来的路径，按照定义计算其安全系数
- 选择所有安全系数中最大的那一个作为答案返回
那么接下来就按照这个步骤逐一进行代码层面的实现。
记录盗贼位置
1 2
n = len(grid) thiefs = [(i, j) for i in range(n) for j in range(n) if grid[i][j]]
找出所有路径
1 2 3 4 5 6 7 8 9 10 11 12 13 14
q = deque([[(0, 0), [(0, 0)], set([(0, 0)])]]) paths = [] while q: cur, path, visited = q.popleft() i, j = cur if i == n - 1 and j == n - 1: paths.append(path) else: for ii, jj in (i+1, j), (i-1, j), (i, j+1), (i, j-1): if 0 <= ii < n and 0 <= jj < n and (ii, jj) not in visited: new_visited = visited.copy() new_visited.add((ii, jj)) q.append([(ii, jj), path + [(ii, jj)], new_visited])
这里探索路径选择了BFS，其中：
q是探索时用于存储信息的队列，内部结构是[当前单元格的坐标, 行进至当前单元格时所走过的路径（包含当前单元格）, 当前路径访问过的单元格（包含当前单元格）]- 为了探索到所有路径，所以对于每一条路径都单独维护一个
visited集合，用于记录当前路径的已访问单元格 i,j,ii,jj分别表示当前单元格的行坐标,当前单元格的列坐标,下一步单元格的行坐标,下一步单元格的列坐标- 当抵达终点
(n-1, n-1)时，将当前路径path添加至路径列表paths中
计算安全系数
1 2 3 4 5 6 7 8 9
def cal_safeness(path, thiefs): safeness = inf for cell in path: i, j = cell for thief in thiefs: thief_i, thief_j = thief d = abs(i - thief_i) + abs(j - thief_j) safeness = min(safeness, d) return safeness
计算最大安全系数
1 2 3 4 5 6 7
ans = 0 for path in paths: safeness = cal_safeness(path, thiefs) ans = max(ans, safeness) return ans
最后将这4个部分拼接起来即可。
复杂度分析
记录盗贼位置
记录盗贼的位置需要完整遍历一次 $n \times n$ 的网格，所以时间复杂度为 $O(n^2)$
找出所有路径
这个部分的时间复杂度分析比想象中要复杂的多，因为此题并不遵循最短路径原则，也就是除了向右和向下之外的剩下两个方向也可以行走，因此最后整个网格内存在的路径数量会非常非常庞大。
不妨想象一下更简单的情况，也就是路径探索只沿着向右和向下的方向（最短路径）的话，那么对于一个 $n \times n$ 的网格来说，从左上角到右下角的最短路径必然由 $n - 1$ 次向下与 $n - 1$ 次向右的探索组成。那么所有可能的路径数 $N$ 便是在 $2n - 2$ 次探索中选择 $n - 1$ 次向右（下）探索的组合数问题，计算方式如下：
\[\begin{aligned} N &= C_{2n - 2}^{n - 1} \\[3mm] &= \frac{(2n - 2)!}{(n - 1)!(n - 1)!} \\[5mm] &= \frac{(n - 1)! \times n \times (n + 1) \times \cdots \times (2n - 2)}{(n - 1)!(n - 1)!} \\[3mm] &= \frac{n \times (n + 1) \times \cdots \times (2n - 2)}{1 \times 2 \times \cdots \times (n - 1)} \\[7mm] O(N) &= O\left(\frac{n \times n \times \cdots \times n}{n!}\right) \\[5mm] &= O\left(\frac{n^{n - 1}}{n!}\right) \end{aligned}\]由此可以得出路径数量的数量级在 $n$ 较小时接近指数级增长，随后增长速度会放缓，低于指数级。但是这仅仅只是遵循最短路径探索原则的情况下的数量级，本题中的情况只会比这更加复杂。这里我们就粗略地假设它的时间复杂度是 $O(2^n)$ 。
（注： 事实上这是一个 自避行走(self-avoiding walk) 问题，目前并没有已知的公式可以解决这个问题）
计算安全系数
计算一条路径的安全系数时，需要对路径上的每一个点进行与周边所有盗贼的距离运算。最坏的情况下，一条路径上的点的数量级可以达到 $O(n^2)$ , 于此同时盗贼的数量级也能达到 $O(n^2)$ , 所以对于单条路径来说，计算该路径安全系数的时间复杂度可以达到 $O(n^4)$ 。
计算最大安全系数
计算最终的答案时，需要比较所有路径的安全系数，故而时间复杂度粗略估计为 $O(2^n n^4)$ 。
BFS + 最佳优先探索 + 二分查找
可以看到最直接的做法的时间复杂度达到了令人瞠目结舌的地步，这显然是无法接受的。接下来我们探讨一下这个做法哪些地方可以进行优化。
关于安全系数
重新审视一下安全系数的定义： 路径上任意一个单元格到任意一名盗贼的最小曼哈顿距离。 我们可以发现，这个距离事实上是单元格的属性，路径的改变只会影响到单元格的选取，而并不会改变这个距离，因为路径的更改并不会使网格发生改变。所以对于原做法可以进行如下优化：
1
对于路径上的每一个单元格计算其与周边盗贼的距离 -> 将单元格与周边盗贼距离的最小值直接存储在网格中
而关于计算这个最小值的方法，我们需要将视角 从单元格转移到盗贼 。相比较从单元格出发计算其与每一个盗贼的距离，从所有存在盗贼的单元格同时出发，利用BFS进行其与周边单元格的距离更新是一个更加效率的做法。这便是利用多源BFS降低时间复杂度的经典做法（关于多源BFS的参考链接）。
代码实现如下：
1 2 3 4 5 6 7 8 9 10
n = len(grid) q = deque([(i, j) for i in range(n) for j in range(n) if grid[i][j]]) def cal_manhattan(): while q: i, j = q.popleft() for ii, jj in (i+1, j), (i-1, j), (i, j+1), (i, j-1): if 0 <= ii < n and 0 <= jj <= n and not grid[ii][jj]: # 空单元格的值为0，同时也表示其尚未被周围最近的盗贼探索到，所以加入探索队列 q.append((ii, jj)) grid[ii][jj] = grid[i][j] + 1 # 更新相邻单元格与最近的盗贼的距离
关于最大安全系数
根据上文的复杂度分析可以看出，原做法中路径的数量因为采取了不加任何限制的探索策略，是数量级最为失控的部分。为了求出题目要求的答案，需要先获得所有路径，再比较这些路径的安全系数。而这里，我们或许也可以转换一下视角：
1 2 3
比较所有路径的安全系数，找出最大的那一个 -> 拟定一个数值，判断是否存在一条路径，其安全系数能够达到该数值，找出这个数值的上界
根据题目的定义，安全系数依托于网格中单元格与盗贼的曼哈顿距离。而对于一个 $n \times n$ 的网格来说，任意单元格与盗贼之间曼哈顿距离的区间可以求出，为： $[0, n - 1]$ 。那么问题就转化成：在该区间内找出满足条件的最大值，条件为存在安全系数为该值的路径。 这个问题可以通过 二分查找 进一步在时间上进行优化，代码如下：
1 2 3 4 5 6 7 8 9 10
low, high = 0, n - 1 while low <= high: mid = low + (high - low) // 2 if # 存在安全系数为mid的路径: low = mid + 1 else: high = mid - 1 return high
关于路径探索
根据前面两部分的分析已经可以看出，对于路径探索的优化方式为：
1
比较任意路径的安全系数 -> 判断指定安全系数下路径的存在性
现在，我们只需要实现一个函数，它可以判断是否存在一条路径，其安全系数不低于指定值。我们需要在当前单元格进行下一步探索时判断是否存在满足如下条件的单元格：
- 不超出网格边界
- 尚未被访问
- 其与最近的盗贼距离不小于指定的安全系数
此外，为了尽可能快地找出满足条件的路径，我们需要 使用一个优先队列来存储待探索的单元格 ，优先度依据 该单元格与终点（网格右下角）的曼哈顿距离 ，距离终点最近的待访问单元格会优先从队列中弹出。实际上这便是 最佳优先搜索(Best-First Search) 算法的实现方式。最佳优先搜索算法是一种 启发式搜索算法，其基于广度优先搜索算法，不同之处在于该方法在对待遍历节点的遍历顺序进行评估时引入了代价函数（对于这道题来说就是节点距终点的曼哈顿距离）。因此，在保存待遍历节点时需要用到优先队列，而不是普通的队列。
整个函数的代码实现如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14
def reachable(safeness_factor): if safeness_factor > grid[0][0] - 1: return False pq = [(2 * n - 2, 0, 0)] # (该单元格与终点的距离, 该单元格的行坐标, 该单元格的列坐标) visited = set() while pq: dis, i, j = heapq.heappop(pq) if i == n - 1 and j == n - 1: return True for ii, jj in (i+1, j), (i-1, j), (i, j+1), (i, j-1): if 0 <= ii < n and 0 <= jj < n and (ii, jj) not in visited and grid[ii][jj] - 1 >= safeness_factor: heapq.heappush(pq, (n - 1 - ii + n - 1 - jj, ii, jj)) visited.add((ii, jj)) return False
注： 上文中定义的
cal_manhattan这个函数对网格中单元格与盗贼的最小曼哈顿距离进行了更新，但是更新的值是基于出发点，也就是盗贼的值1往上叠加的，所以真实的距离需要对全体单元格减1。（当然这一步在全局实现会更好）
至此，整个算法的优化便完成了，最终我们将三个部分拼接，并添加一些特判进一步优化该算法的效率。结果如下：
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
class Solution:
def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
if grid[0][0] or grid[-1][-1]:
return 0
n = len(grid)
q = deque([(i, j) for i in range(n) for j in range(n) if grid[i][j]])
def cal_manhattan():
while q:
i, j = q.popleft()
for ii, jj in (i+1, j), (i-1, j), (i, j+1), (i, j-1):
if 0 <= ii < n and 0 <= jj < n and not grid[ii][jj]: # 空单元格的值为0，同时也表示其尚未被周围最近的盗贼探索到，所以加入探索队列
q.append((ii, jj))
grid[ii][jj] = grid[i][j] + 1 # 更新相邻单元格与最近的盗贼的距离
def reachable(safeness_factor):
if safeness_factor > grid[0][0] - 1:
return False
pq = [(2 * n - 2, 0, 0)] # (该单元格与终点的距离, 该单元格的行坐标, 该单元格的列坐标)
visited = set()
while pq:
dis, i, j = heapq.heappop(pq)
if i == n - 1 and j == n - 1:
return True
for ii, jj in (i+1, j), (i-1, j), (i, j+1), (i, j-1):
if 0 <= ii < n and 0 <= jj < n and (ii, jj) not in visited and grid[ii][jj] - 1 >= safeness_factor:
heapq.heappush(pq, (n - 1 - ii + n - 1 - jj, ii, jj))
visited.add((ii, jj))
return False
cal_manhattan()
low, high = 1, n - 1
while low <= high:
mid = low + (high - low) // 2
if reachable(mid):
low = mid + 1
else:
high = mid - 1
return high
结果顺利通过。
