Leetcode - 深度 and 广度优先搜索（一）

286. 墙与门

https://leetcode-cn.com/problems/walls-and-gates/

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

-1 表示墙或是障碍物
0 表示一扇门
INF 无限表示一个空的房间。然后，我们用 231 - 1 = 2147483647 代表 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

题解

一：从空房间出发，广度优先遍历寻找距每一个空房间最近的门（寻找的过程O(mn)）， 每一个空房间都要做一次广度遍历，需要O(mn)的广度遍历，最终的时间复杂度O(m^2n^2)。

二：从门出发，先遍历一遍数组将所有的门入队。从门开始做广度遍历，每个空房间只要遍历一遍，时间复杂度O(mn)。由于宽度优先搜索保证我们在搜索 d + 1 距离的位置时， 距离为 d 的位置都已经被搜索过了，所以到达每一个房间的时候都一定是最短距离。

from collections import deque
class Solution(object):
    def wallsAndGates(self, rooms):
        """
        :type rooms: List[List[int]]
        :rtype: None Do not return anything, modify rooms in-place instead.
        """
        def inArea(i, j, m, n):
            return 0 <= i < m and 0 <= j < n

        if not rooms or not rooms[0]:
            return 
        
        m, n = len(rooms), len(rooms[0])
        visited = [[False] * n for _ in range(m)]
        q = deque()

        for i in range(m):
            for j in range(n):
                if rooms[i][j] == 0:
                    q.append([i, j])
                    visited[i][j] = True

        pos = [[0, 1], [1, 0], [0, -1], [-1, 0]]
        dis = 1

        while q:
            length = len(q)
            for i in range(length):
                idx, idy = q.popleft()
                for j in range(4):
                    newx, newy = idx + pos[j][0], idy + pos[j][1]
                    
                    if (inArea(newx, newy, m, n) and rooms[newx][newy] > 0 
                         and not visited[newx][newy]):
                        visited[newx][newy] = True
                        q.append([newx, newy])
                        rooms[newx][newy] = dis 
            dis += 1

        return