题目

给定一个 m × n 的二维网格，网格中有以下三种可能的初始化值：

• -1 表示墙或是障碍物
• 0 表示一扇门
• INF 无限表示一个空的房间。然后，我们用 代表 INF。你可以认为通往门的距离总是小于 2147483647 的。

现在要给每个空房间位上填上 该房间到最近门的距离，如果无法到达门，则填 INF 即可。

示例：
给定二维网格：

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

运行完你的函数后，该网格应该变成：

3  -1   0   1
2   2   1  -1
1  -1   2  -1
0  -1   3   4

方案一

class Solution:
    def wallsAndGates(self, rooms: [[int]]) -> None:
        """
        Do not return anything, modify rooms in-place instead.
        """
        self.rooms = rooms
        self._coor_path = {}  # key: 起始坐标 value: 到门的最短路径长度
        for i in range(len(rooms)):
            for j in range(len(rooms[0])):
                if rooms[i][j] == 0 or rooms[i][j] == -1:  # 跳过门和墙
                    continue
                if (i, j) not in self._coor_path:
                    self._set_coor_path_use_bfs((i, j))
                rooms[i][j] = self._coor_path[(i, j)]

    def _set_coor_path_use_bfs(self, coordinate):
        deque = collections.deque([coordinate])
        used = {coordinate}
        step = 0
        path = []  # (当前节点, 下一步节点), 获取最短路径时通过此结构获取

        while len(deque) > 0:
            step += 1
            for _ in range(len(deque)):
                coor = deque.popleft()
                if self.rooms[coor[0]][coor[1]] == 0:  # 是最终节点(门)
                    self._set_path(path, coor)
                    return

                next_coors = self._get_round_coordinate(coor)
                for next_coor in next_coors:
                    if next_coor not in used:
                        used.add(next_coor)
                        deque.append(next_coor)
                        path.append((coor, next_coor))

        # 没有找到终点
        self._coor_path[coordinate] = 2147483647

    def _set_path(self, path, end_coor):
        '''
        设置最短路径

        params:
            path: [前一个坐标, 接下来的坐标]
            end_coor: 结束坐标
        '''
        min_path = [end_coor]
        for i in range(len(path) - 1, -1, -1):
            if end_coor == path[i][1]:
                min_path.append(path[i][0])
                end_coor = path[i][0]

        for j in range(len(min_path) - 1, 0, -1):
            if min_path[j] not in self._coor_path:
                self._coor_path[min_path[j]] = j

    def _get_round_coordinate(self, coordinate=(None, None)):
        '''返回周围的坐标'''
        ret = [
            (coordinate[0], coordinate[1] - 1),
            (coordinate[0], coordinate[1] + 1),
            (coordinate[0] - 1, coordinate[1]),
            (coordinate[0] + 1, coordinate[1])
        ]

        def _is_coordinate_satify(coordinate):
            if coordinate[0] >= 0 and coordinate[0] < len(self.rooms) and coordinate[1] >= 0 and coordinate[1] < len(self.rooms[0]):
                if self.rooms[coordinate[0]][coordinate[1]] == -1:  # 墙不能直接通过
                    return False
                return True
            return False

        return filter(_is_coordinate_satify, ret)

• 直接使用bfs，唯一的优化点是在执行一个bgs的过程中计算好路径上的所有距离
• 性能极差

方案二

class Solution:
    def wallsAndGates(self, rooms: [[int]]) -> None:
        """
        Do not return anything, modify rooms in-place instead.
        """
        if not rooms or len(rooms) == 0:
            return rooms
        INF = 2 ** 31 - 1
        m, n = len(rooms), len(rooms[0])
        doors = [(i, j) for i in range(m) for j in range(n) if rooms[i][j] == 0] # 找到所有门
        for i, j in doors:
            for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)): # 循环周围的坐标
                if 0 <= x < m and 0 <= y < n and rooms[x][y] == INF:
                    rooms[x][y] = rooms[i][j] + 1
                    doors.append((x, y)) # 这一行, 利用列表for循环特性, 完美的执行了递归的过程

上述答案为leetcode上执行效率最高的答案

1. 使用反向思维, 从门开始向外拓展
2. 利用 for 循环的特性, 以及 rooms 起始值为 0, 巧妙的避免了递归

   原文

   https://leetcode-cn.com/explore/learn/card/queue-stack/217/queue-and-bfs/871/