LeetCode 286 Walls and Gates

LeetCode

You are given an m x n grid rooms initialized with these three possible values.

-1 A wall or an obstacle. 0 A gate.
INF Infinity means an empty room. We use the value 2<sup>31</sup> - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

Example 1:

Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

Example 2:

Input: rooms = [[-1]]
Output: [[-1]]

Constraints: m == rooms.length
n == rooms[i].length 1 <= m, n <= 250
* rooms[i][j] is -1, 0, or 2<sup>31</sup> - 1.

题目大意：

求所有房间到门的最短距离

解题思路：

属于多始点BFS类型

解题步骤：

N/A

注意事项：

门的距离不更新，所以出列后要判断该点是否为门，不是用距离来判断

Python代码：

OFFSET = [(-1, 0), (1, 0), (0, 1), (0, -1)]
class Solution(TestCases):

    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        """
        Do not return anything, modify rooms in-place instead.
        """
        gates = []
        for i in range(len(rooms)):
            for j in range(len(rooms[0])):
                if rooms[i][j] == 0:
                    gates.append((i, j, 0))
        queue = collections.deque(gates)
        visited = set(gates)
        while queue:
            x, y, distance = queue.popleft()
            if rooms[x][y] != 0: # not distance != 0
                rooms[x][y] = distance
            for _dx, _dy in OFFSET:
                _x, _y = x + _dx, y + _dy
                if _x < 0 or _x >= len(rooms) or _y < 0 or _y >= len(rooms[0]) or \
                        rooms[_x][_y] == -1 or (_x, _y) in visited:
                    continue
                queue.append((_x, _y, distance + 1))
                visited.add((_x, _y))

算法分析：

时间复杂度为O(nm)，空间复杂度O(mn)