难度: Medium
Submission
运行时间: 67 ms
内存: 19.5 MB
class Solution:
def wallsAndGates(self, rooms: List[List[int]]) -> None:
"""
Do not return anything, modify rooms in-place instead.
"""
m = len(rooms)
n = len(rooms[0])
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
inf = 2**31 - 1
search_queue = deque()
for x in range(m):
for y in range(n):
if rooms[x][y] == 0:
search_queue.append((x, y))
while search_queue:
x, y = search_queue.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if m > nx >= 0 and n > ny >= 0 and rooms[nx][ny] == inf:
rooms[nx][ny] = rooms[x][y] + 1
search_queue.append((nx, ny))
Explain
这个题解使用广度优先搜索(BFS)的方法来解决问题。首先，遍历整个rooms矩阵，找到所有的门(值为0的格子)，并将它们的坐标添加到一个队列search_queue中。然后，不断从队列中取出格子，对于每个格子，检查其四个相邻的格子。如果相邻格子是空的(值为inf)，就将其距离设置为当前格子的距离+1，并将相邻格子加入队列。这样不断扩展，直到队列为空，所有可达的空格子都被填入正确的距离值。
时间复杂度: O(m*n)
空间复杂度: O(m*n)
class Solution:
def wallsAndGates(self, rooms: List[List[int]]) -> None:
"""
Do not return anything, modify rooms in-place instead.
"""
m = len(rooms)
n = len(rooms[0])
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 定义四个方向
inf = 2**31 - 1 # 定义无限大的值
search_queue = deque() # 初始化BFS队列
# 遍历矩阵，找到所有的门并加入队列
for x in range(m):
for y in range(n):
if rooms[x][y] == 0:
search_queue.append((x, y))
# BFS过程
while search_queue:
x, y = search_queue.popleft() # 取出队首格子
for dx, dy in directions: # 遍历四个方向
nx, ny = x + dx, y + dy # 计算相邻格子坐标
# 检查相邻格子是否在矩阵范围内且为空格子
if m > nx >= 0 and n > ny >= 0 and rooms[nx][ny] == inf:
rooms[nx][ny] = rooms[x][y] + 1 # 更新相邻格子的距离为当前格子距离+1
search_queue.append((nx, ny)) # 将相邻格子加入队列
Explore
在BFS解法中，一开始只将门的位置加入搜索队列是因为门是距离计算的起点，门的位置本身的距离值为0，代表最短距离的起始点。从门开始，逐步向外扩展到相邻的格子，能够保证每一个空格子被计算的距离都是从最近的门开始计算的最短距离。如果一开始将所有格子都加入队列，将无法保证逐层扩展的过程中能够正确计算出每个空格子至最近门的最短距离，且会增加不必要的计算复杂度和资源消耗。
在BFS扩展过程中，由于每个格子在被发现并加入队列时其距离就已经被设定为从起点到该点的最短距离，因此不会出现重复更新同一个格子的情况。一旦格子的距离被设置并加入队列，其距离就是确定的，后续不会有来自其他路径的更新覆盖这个距离。这种方法确保了每个格子的距离值只被计算一次，从而提高算法的效率，避免不必要的重复计算。
当矩阵中不包含任何门时，由于搜索队列初始为空，BFS过程实际上不会执行任何操作。这种情况下，所有格子的值（如果原始值为inf）将保持不变，因为没有门可以作为起点来更新距离。在这种特殊情况下，算法已经足够有效，因为它不会进行任何无效的操作或计算。因此，没有必要对这种情况进行特殊处理，因为算法本身在没有门时不会执行距离更新，这已经是效率最优的处理方式。