542. 01 Matrix

Medium (Trung bình) Python 🔗 Xem trên LeetCode

📋 Đề Bài

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

 

Example 1:

Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]

Example 2:

Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]

 

Constraints:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 104
  • 1 <= m * n <= 104
  • mat[i][j] is either 0 or 1.
  • There is at least one 0 in mat.

🧠 Thuật Toán & Kỹ Thuật

Matrix (Ma trận)
⏱️ Thời gian O(n²)
💾 Không gian O(n)

💻 Lời Giải

Python 0542-01-matrix.py 
class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        r, c = len(mat), len(mat[0])
        
        dq = deque([])
        
        for i in range(r):
            for j in range(c):
                if mat[i][j] == 0:
                    dq.append((i, j))
                else:
                    mat[i][j] = -1
        
        DIR = [-1, 0, 1, 0, -1]
        
        while dq:
            n = len(dq)
            x, y = dq.popleft()
            
            for i in range(4):
                xx = x + DIR[i]
                yy = y + DIR[i + 1]
                
                if 0 <= xx < r and 0 <= yy < c and mat[xx][yy] == -1:
                    dq.append((xx, yy))
                    mat[xx][yy] = mat[x][y] + 1
                    
        return mat