image.png

輸入：rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
輸出：[[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

示例 2：
輸入：rooms = [[-1]]
輸出：[[-1]]

示例 3：
輸入：rooms = [[2147483647]]
輸出：[[2147483647]]

示例 4：
輸入：rooms = [[0]]
輸出：[[0]]

Solution:

class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        """
        Do not return anything, modify rooms in-place instead.
        """
        row = len(rooms)
        col = len(rooms[0])
        
        def bfs(i, j, step): 
            nonlocal row, col
            if i < 0 or i > row -1 or j < 0 or j > col - 1:
                return
            if rooms[i][j] <= step and step != 0 : 
                return
            rooms[i][j] = step
            
            bfs(i + 1, j, step + 1)
            bfs(i, j + 1, step + 1)
            bfs(i - 1, j, step + 1)
            bfs(i, j - 1, step + 1)
            
        for i in range(row):
            for j in range(col):
                if rooms[i][j] == 0:
                    bfs(i, j, 0)

解題思路：
本題目主要考察bfs(廣度優(yōu)先搜索)，一般這種找最短距離的，用bfs比較直觀。那么什么是BFS呢，Breadth First Search，優(yōu)先訪問當(dāng)前結(jié)點相鄰的點，如下圖所示，數(shù)字表示訪問的順序

BFS.png

簡單的來說：

1. 先訪問1，然后23待命
2. 1訪問完，訪問2，此時與2相鄰的45也加入待命的隊列，這時候待訪問的有345
3. 2訪問完，訪問3（23與1相鄰），接著56加入待命的隊列，此時待訪問的有456
4. 與1相鄰的訪問完了，下面訪問4，7加入待訪問隊列，待訪問的有567
5. 同理，5訪問完，待訪問的有678
6. 6訪問完，待訪問的有7、8
7. 7 訪問完，待訪問的有8、9、10
8. 8訪問完，待訪問的有9、10、 11
9. 剩下的就按順序訪問完
   所以bfs就像走一棵樹一樣，一層一層訪問，待訪問的點都是推與當(dāng)前點相鄰結(jié)點。

回到本題目，我們要找到，每個空格離門最近的距離，那不就相當(dāng)于我們從門到空格經(jīng)歷了幾層嗎。拿示例1舉個??

image.png

從左下角的門，我們只能向上走一步（右邊是墻走不通），因此門上一空格為①，接著走，我們只能再往上走（右邊是墻），因此門上二空格為②，再從這個空格我們繼續(xù)往四周走，可以向上，向右走，因此這兩個空格我標(biāo)③，就這么一直走，像樹蔓延一樣，我們得到了每個空格離左下門的距離（左圖）。
我們用相同的方法走右上的門，標(biāo)出每個空格離右上們的距離（右圖）。
最后比較一下每個空格的數(shù)字大小，留下數(shù)字小的，就是離門最近的距離。
總之，四個方向，遇到墻走不通，不回頭。

代碼邏輯：

1. 找grid[i][j] == 0，做bfs的遞歸，注意邊界，只要你往下走就做一層遞歸，step+1
2. 如果rooms[i][j]<=step，就不要繼續(xù)往下走了
3. 多個門，只要你當(dāng)前的step是小于已經(jīng)記錄下來的rooms[i][j]，那就替換