难度: Hard
Submission
运行时间: 1352 ms
内存: 16.3 MB
class Solution:
def shortestDistance(self, grid: List[List[int]]) -> int:
directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
m, n = len(grid), len(grid[0])
dist = [[0 for _ in range(n)] for _ in range(m)]
buildings = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
q = deque()
q.append([i,j])
dis = 1
while q:
le = len(q)
for _ in range(le):
x, y = q.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == buildings:
grid[nx][ny] -= 1
dist[nx][ny] += dis
q.append([nx, ny])
dis += 1
buildings -= 1
# print(dist)
res = float('inf')
for i in range(m):
for j in range(n):
if grid[i][j] == buildings:
res = min(res, dist[i][j])
return res if res != float('inf') else -1
Explain
该题解采用BFS（广度优先搜索）的方法。首先遍历网格，找到所有建筑物的位置，然后以每个建筑物为起点进行BFS。在BFS过程中，记录每个空地到当前建筑物的距离，并将距离累加到dist数组中。同时，将访问过的空地标记为负数，避免重复访问。最后，遍历dist数组，找到到所有建筑物距离之和最小的空地，返回其距离和。如果没有符合条件的空地，则返回-1。
时间复杂度: O(b*m*n)，其中b为建筑物的数量
空间复杂度: O(m*n)
class Solution:
def shortestDistance(self, grid: List[List[int]]) -> int:
directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
m, n = len(grid), len(grid[0])
dist = [[0 for _ in range(n)] for _ in range(m)] # 存储每个空地到所有建筑物的距离之和
buildings = 0 # 建筑物的数量
# 遍历网格，找到所有建筑物的位置
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
q = deque()
q.append([i,j])
dis = 1
# 从当前建筑物开始BFS
while q:
le = len(q)
for _ in range(le):
x, y = q.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
# 如果在网格范围内且为未访问过的空地
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == buildings:
grid[nx][ny] -= 1 # 标记为已访问
dist[nx][ny] += dis # 累加距离
q.append([nx, ny])
dis += 1
buildings -= 1
res = float('inf')
# 遍历dist数组，找到距离和最小的空地
for i in range(m):
for j in range(n):
if grid[i][j] == buildings:
res = min(res, dist[i][j])
return res if res != float('inf') else -1
Explore
在BFS过程中，将访问过的空地标记为负数是为了防止同一层或不同层的BFS重复访问同一个空地，从而导致不必要的计算和错误的距离累加。这种标记方式利用了原始网格数组，减少了额外空间的需求，也使得状态的更新（即标记为空地已访问）与检查（是否已访问过）更为直接和高效。相比于使用额外的visited数组来记录访问状态，这种方法节省了空间并简化了代码逻辑。
在BFS过程中，`dis`变量在每完成一层的遍历后增加1。由于BFS按层遍历，每一层的所有节点都与起点的距离相同，并且比上一层每个节点的距离多1。因此，通过这种逐层增加的方式，`dis`能够准确地反映从起点到当前节点的实际距离。这保证了无论何时将一个新节点加入队列，其记录的距离都是正确的。
在算法中，每遍历到一个建筑物，会将当前建筑物的标记值（开始为1）递减（变为0，然后-1，依此类推）。当BFS从一个建筑物开始时，只有那些标记值等于当前建筑物标记的空地才能被访问和更新。因此，每个空地只会与当前正在进行BFS的建筑物关联一次，确保每个空地到不同建筑物的距离只被计算一次。这通过动态地调整grid中的值来防止重复访问和重复计算。
在这个算法中，从哪个建筑物开始BFS并不影响最终结果，因为算法的目标是计算每个空地到所有建筑物的距离总和。算法确保了每个空地都会被每个建筑物访问一次，无论BFS的起始顺序如何。因此，不需要特别考虑从某个特定建筑物开始的问题。所有建筑物最终都会均等地对结果产生影响，确保了计算的公正性和正确性。