542. 01 Matrix
BFS, Array, DP, Matrix, Review ·Problem Statement
link: LeetCode.cn LeetCode
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:
Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]
Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]
Solution Approach
BFS Approach: Utilizes Breadth-First Search to traverse the matrix from zero cells outward, updating the distance for each non-zero cell by exploring its neighboring cells iteratively.
DP Approach: Employs Dynamic Programming to iteratively update the distance of each cell by considering its adjacent cells, resulting in a matrix with the distance of each cell from the nearest zero.
Algorithm
Breadth-First Search (BFS):
Start by finding all cells with value 0 and enqueue them into a queue. Initialize a result matrix with all zeros. Iterate through the queue: Pop a cell from the queue and explore its neighboring cells. For each neighbor, update its distance in the result matrix if it’s not visited yet. Enqueue the unvisited neighboring cells. Return the result matrix.
Dynamic Programming (DP):
Initialize a distance matrix with all elements initialized to a maximum value. Iterate through the matrix: If the cell value is 0, set its distance to 0. Update distances from top-left to bottom-right direction: Update distances considering top and left cells. Update distances from bottom-right to top-left direction: Update distances considering bottom and right cells. Return the distance matrix.
Implement
class Solution:
def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
m, n = len(mat), len(mat[0])
res = [[0] * n for _ in range(m)]
zeroes = [for i in range(m) for j in range(n) if mat[i][j] == 0]
q = collections.deque(zeroes)
visited = set(zeroes)
while q:
i, j = q.popleft()
for ni, nj in [(1,0),(0,1),(-1,0),(0,-1)]:
if 0 <= ni < m and 0<= nj < n and (ni, nj) not in visited:
res[ni][nj] = res[i][j] + 1
q.append((ni, nj))
visited.add((ni, nj))
return res
class Solution:
def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
m, n = len(mat), len(mat[0])
dist = [[m + n] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if mat[i][j] == 0:
dist[i][j] = 0
for i in range(m):
for j in range(n):
if i - 1 >= 0:
dist[i][j] = min(dist[i][j], dist[i - 1][j] + 1)
if j - 1 >= 0:
dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1)
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
if i + 1 < m:
dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1)
if j + 1 < n:
dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1)
return dist