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]]
- code
class Solution:
def updateMatrix(self, matrix):
m, n = len(matrix), len(matrix and matrix[0])
for i in range(m):
for j in range(n):
if matrix[i][j] != 0:
matrix[i][j] = float("inf")
if i > 0 and matrix[i - 1][j] + 1 < matrix[i][j]:
matrix[i][j] = matrix[i - 1][j] + 1
if j > 0 and matrix[i][j - 1] + 1 < matrix[i][j]:
matrix[i][j] = matrix[i][j - 1] + 1
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
if matrix[i][j] != 0:
if i + 1 < m and matrix[i + 1][j] + 1 < matrix[i][j]:
matrix[i][j] = matrix[i + 1][j] + 1
if j + 1 < n and matrix[i][j + 1] + 1 < matrix[i][j]:
matrix[i][j] = matrix[i][j + 1] + 1
return matrix
- code
class Solution:
def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
visited = set()
from collections import deque
q = deque()
for i in range(len(mat)):
for j in range(len(mat[0])):
if mat[i][j] == 0:
visited.add((i,j))
q.append((i,j))
while q:
x,y = q.popleft()
for dirr in [(1,0), (-1,0), (0,1), (0,-1)]:
newX, newY = x+dirr[0], y+dirr[1]
if newX >= 0 and newX <= len(mat)-1 and newY >= 0 and newY <= len(mat[0])-1 and (newX, newY) not in visited:
mat[newX][newY] = mat[x][y] + 1
visited.add((newX, newY))
q.append((newX, newY))
return mat
- code
class Solution:
def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
import collections
m = len(mat)
n = len(mat[0])
def findZero(row, col):
q = deque()
q.append(((row, col), 0))
visited = set()
while q:
qsize = len(q)
for _ in range(qsize):
rc, d = q.popleft()
r, c = rc
if r < 0 or r >= m or c < 0 or c >= n:
continue
if mat[r][c] == 0:
return d
visited.add((r,c))
if (r-1, c) not in visited:
q.append(((r-1, c), d+1))
if (r+1, c) not in visited:
q.append(((r+1, c), d+1))
if (r, c-1) not in visited:
q.append(((r, c-1), d+1))
if (r, c+1) not in visited:
q.append(((r, c+1), d+1))
for row in range(m):
for col in range(n):
if mat[row][col] == 1:
step = findZero(row, col)
mat[row][col] = step
return mat