九章算法 | Google 面试题：Police Distance - 杂谈

答案：本题可通过多起点广度优先搜索（BFS）解决，将所有警察的位置作为起点同时进行搜索，计算每个空地到最近警察的距离。

解题步骤

初始化队列和距离矩阵
遍历输入矩阵，将所有警察的位置（值为1的格子）加入队列，并记录这些位置的距离为0。
初始化一个与输入矩阵大小相同的距离矩阵dist，警察位置的距离为0，墙（值为-1）的距离设为-1（表示不可达），空地（值为0）的距离初始化为一个极大值（如INF）。
多起点BFS
从队列中取出当前位置，检查其四个相邻方向（上、下、左、右）的格子：
如果相邻格子是空地且未被访问过（即dist中的值为INF），则更新其距离为当前距离+1，并将其加入队列。
墙（值为-1）直接跳过。
重复上述过程直到队列为空。
输出结果
最终dist矩阵即为每个空地到最近警察的距离，墙的位置保持-1不变。

代码实现（Python示例）from collections import dequedef police_distance(matrix): if not matrix or not matrix[0]: return [] n, m = len(matrix), len(matrix[0]) dist = [[float('inf')] * m for _ in range(n)] q = deque() # 初始化：将所有警察位置加入队列，并设置距离为0 for i in range(n): for j in range(m): if matrix[i][j] == 1: dist[i][j] = 0 q.append((i, j)) elif matrix[i][j] == -1: dist[i][j] = -1 # 墙不可达 # 四个移动方向 directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] while q: x, y = q.popleft() for dx, dy in directions: nx, ny = x + dx, y + dy if 0 <= nx < n and 0 <= ny < m and matrix[nx][ny] == 0 and dist[nx][ny] == float('inf'): dist[nx][ny] = dist[x][y] + 1 q.append((nx, ny)) return dist# 示例输入matrix = [ [0, 1, 0, 0], [0, -1, 0, 1], [0, 0, 0, -1]]result = police_distance(matrix)for row in result: print(row)关键点分析

多起点BFS的优势
相比对每个警察单独进行BFS并取最小值，多起点BFS只需一次遍历，时间复杂度为O(n×m)，效率更高。
边界条件处理
墙的位置（值为-1）需标记为不可达（距离设为-1）。
空地的初始距离设为INF，确保第一次访问时能正确更新为最小值。
队列的作用
队列中存储的是当前层级的格子，保证每次处理的都是距离起点最近的格子，从而避免重复计算。

示例输出

对于输入矩阵：

[ [0, 1, 0, 0], [0, -1, 0, 1], [0, 0, 0, -1]]

输出结果为：

[1, 0, 1, 1][2, -1, 2, 0][3, 2, 1, -1]

例如，位置(0,0)的值为1，表示距离最近的警察（(0,1)）的距离为1。

总结

本题通过多起点BFS高效解决了空地到最近警察的距离计算问题，核心在于将所有警察位置作为起点同时搜索，避免重复计算。代码实现中需注意边界条件和队列的更新逻辑。

九章算法 | Google 面试题：Police Distance

您可能感兴趣问答

Collapsible

热门标签

热点问答