LeetCode 542. 01 矩陣

文章目錄

• • • 542. 01 矩陣
    • • 題目
      • 解題思路
      • 代碼實作
      • 實作結果

542. 01 矩陣

題目來源：https://leetcode-cn.com/problems/01-matrix

題目

給定一個由 0 和 1 組成的矩陣，找出每個元素到最近的 0 的距離。

兩個相鄰元素間的距離為 1 。

示例 1:

輸入:

0 0 0
0 1 0
0 0 0
           

輸出:

0 0 0
0 1 0
0 0 0
           

示例 2:

輸入:

0 0 0
0 1 0
1 1 1
           

輸出:

0 0 0
0 1 0
1 2 1
           

注意:

• 給定矩陣的元素個數不超過 10000。
• 給定矩陣中至少有一個元素是 0。
• 矩陣中的元素隻在四個方向上相鄰: 上、下、左、右。

解題思路

思路：廣度優先搜尋

可以從 0 的位置開始進行廣度優先搜尋。

将 0 視為源點，将其都入隊，各個 0 向 1 擴散（在這裡每個 1 都是被離它最近的 0 擴散到的）。

擴散的時候要注意，在傳回的矩陣中，可以在對應的坐标中設定距離值，同時标記是否通路過。需要注意的是其中 0 元素距離為 0，在建構傳回矩陣時，設預設初始值為 0，這個時候，可以直接将源點 0 放入已标記部分。

具體看下面代碼實作。

代碼實作

class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        m, n = len(matrix), len(matrix[0])

        # 建構傳回矩陣
        ans = [[0] * n for _ in range(m)]
        # 先找所有源點 0 的位置
        zero = [(i, j) for i in range(m) for j in range(n) if matrix[i][j] == 0]
        # 将所有源點 0 入隊列
        from collections import deque
        queue = deque(zero)
        # 标記
        # 這裡将源點 0 的位置加入标記
        # 是因為源點 0 的距離就是 0
        # 可不做變化，傳回矩陣預設初始值為 0
        sign = set(queue)

        # 需擴散的四個方位
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        while queue:
            # 出隊列，進行擴散
            i, j = queue.popleft()
            for di, dj in directions:
                ni, nj = i + di, j + dj
                if 0<=ni<m and 0<=nj<n and (ni, nj) not in sign:
                    ans[ni][nj] = ans[i][j] + 1
                    queue.append((ni, nj))
                    sign.add((ni, nj))

        return ans
           

實作結果

以上就是使用廣度優先搜尋的方法，找出源點 0 的位置進行擴散，進而解決《542. 01 矩陣》的主要内容，需要注意的是擴散的同時，需要标記哪部分已經擴散到的。

歡迎關注微信公衆号《書所集錄》