【Leetcode解題】542. 01 Matrix

題目

• 題目連結
• 目標函式 : updateMatrix(mat)
  • Input : mat: List[List[int]]
  • Output : List[List[int]]

解題概念

• 題意 : 給定一 m $\times$ n 的二元陣列 mat，需要回傳每格離最近的0之距離
  • 兩相鄰格之間的距離為 1

我的寫法

• 想法 :

  1. 使用DFS，從正中心開始往外探索
  2. 使用陣列 check 去紀錄當前探索的狀況
     • 若該格尚未被探索過，則標記為 -1
  3. 探索的判斷式為 : DFS(i, j) = min(DFS(i-1, j), DFS(i+1, j), DFS(i, j-1), DFS(i, j+1))

• 遇到之困難 : 發現超過 maximum recursion depth

解答 or 其他優秀寫法

• 想法 : 應該使用 BFS
  • Stage 1 :
    • 先將 mat 中非0的格子全部指定為 -1
    • 同時，將為0的格子都加入到 Queue 中
  • Stage 2 : 執行 BFS
    • pop 一個格子出來，並判斷他上下左右的格子
    • 若判斷一格子尚未處理，則將其加回到 Queue 中
  • 這邊解題者使用了一個很漂亮的寫法 :
    • 平常若要去探索 mat[r][c] 上下左右的格子，會各自對 mat[r-1][c]、mat[r+1][c]、mat[r][c-1] 與 mat[r][c+1] 進行處裡
    • 但這邊解題者先是宣告了 DIR = [0, 1, 0, -1, 0]
    • 然後在要探索的時候，執行一 for 迴圈 :

      r, c = q.popleft()
      for i in range(4):
          nr, nc = r + DIR[i], c + DIR[i + 1]
          # ...

    • 這種寫法可以快速處理上下左右的格子，非常漂亮!
• 程式碼 :

  def updateMatrix(self, mat):
  
      m = len(mat)
      n = len(mat[0])
      DIR = [0, 1, 0, -1, 0]
  
      q = deque([])
  
      # Stage 1
      for r in range(m):
          for c in range(n):
              if mat[r][c] == 0:
                  q.append((r, c))
              else:
                  mat[r][c] = -1  # Marked as not processed yet!
  
      # Stage 2
      while q:
          r, c = q.popleft()
          for i in range(4):
              nr, nc = r + DIR[i], c + DIR[i + 1] # nr, nc 代表當前4個方向的其中一個
              if nr < 0 or nr == m or nc < 0 or nc == n or mat[nr][nc] != -1: 
                  # 處理邊界值 and 已探索過的格子
                  continue
              mat[nr][nc] = mat[r][c] + 1 # 該距離 + 1
              q.append((nr, nc)) # 將該格子加回 queue 中
      
      return mat

• 成效 :
  • Time Complexity : $O(m\times n)$
  • Runtime: 510 ms (faster than 59.71%)
  • Memory Usage: 15.97 MB (more than 83.47%)