Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.
Example 1:
Input:
[[0,0,0],
[0,1,0],
[0,0,0]]
Output:
[[0,0,0],
[0,1,0],
[0,0,0]]
Example 2:
Input:
[[0,0,0],
[0,1,0],
[1,1,1]]
Output:
[[0,0,0],
[0,1,0],
[1,2,1]]
Note:
- The number of elements of the given matrix will not exceed 10,000.
- There are at least one 0 in the given matrix.
- The cells are adjacent in only four directions: up, down, left and right.
Solutions
1. DP
DP，设dp[i][j]为最小距离，从左上角到右下角跑一次，然后从右下角到左上角跑一次即可。
class Solution(object):
def updateMatrix(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[List[int]]
"""
if not matrix: return [[]]
m, n = len(matrix), len(matrix[0])
dp = [[0x7fffffff if matrix[i][j] != 0 else 0 for j in range(n)] for i in range(m)]
for i in range(m):
for j in range(n):
self.DP(i, j, m, n, dp)
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
self.DP(i, j, m, n, dp)
return dp
def DP(self, i, j, m, n, dp):
if i > 0: dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1)
if j > 0: dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1)
if i < m - 1: dp[i][j] = min(dp[i][j], dp[i + 1][j] + 1)
if j < n - 1: dp[i][j] = min(dp[i][j], dp[i][j + 1] + 1)
# Runtime: 1036 ms, faster than 11.29% of Python3 online submissions for 01 Matrix.
# Memory Usage: 16.7 MB, less than 8.33% of Python3 online submissions for 01 Matrix.
2. DFS
class Solution:
def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
if not matrix:
return matrix
self.r, self.c = len(matrix), len(matrix[0])
self.directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for i in range(self.r):
for j in range(self.c):
if matrix[i][j] == 1 and (not self.has_neighbor_zero(i, j, matrix)):
matrix[i][j] = float('inf')
for i in range(self.r):
for j in range(self.c):
if matrix[i][j] == 1:
self.dfs(matrix, i, j, -1)
return matrix
def has_neighbor_zero(self, row, col, matrix):
for dire in self.directions:
x, y = row + dire[0], col + dire[1]
if x >= 0 and x < self.r and y >= 0 and y < self.c and matrix[x][y] == 0:
return True
return False
def dfs(self, matrix, row, col, val):
if row < 0 or row >= self.r or col < 0 or col >= self.c or matrix[row][col] <= val:
return
if val > 0:
matrix[row][col] = val
for dire in self.directions:
x, y = row + dire[0], col + dire[1]
self.dfs(matrix, x, y, matrix[row][col] + 1)
# Runtime: 848 ms, faster than 37.41% of Python3 online submissions for 01 Matrix.
# Memory Usage: 16 MB, less than 25.00% of Python3 online submissions for 01 Matrix.
上面这种解法不是很好理解，换一种。
class Solution:
def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
if not matrix:
return matrix
self.r, self.c = len(matrix), len(matrix[0])
self.directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
res = [[float('inf') for _ in range(self.c)] for _ in range(self.r)]
for i in range(self.r):
for j in range(self.c):
if matrix[i][j] == 0:
self.dfs(matrix, res, i, j, 0)
return res
def dfs(self, matrix, res, row, col, dist):
if row < 0 or row >= self.r or col < 0 or col >= self.c or res[row][col] <= dist:
return
if matrix[row][col] == 0:
dist = 0
res[row][col] = dist
for dire in self.directions:
x, y = row + dire[0], col + dire[1]
self.dfs(matrix, res, x, y, dist + 1)
这个会 TLE，结果还是必须要用第一种方法，先判断是否有临近的 0 才行：
class Solution:
def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
if not matrix:
return matrix
self.r, self.c = len(matrix), len(matrix[0])
self.directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for i in range(self.r):
for j in range(self.c):
if matrix[i][j] == 1 and not self.has_neighbor_zero(i, j, matrix):
matrix[i][j] = float('inf')
for i in range(self.r):
for j in range(self.c):
self.dfs(matrix, i, j)
return matrix
def has_neighbor_zero(self, row, col, matrix):
for dire in self.directions:
x, y = row + dire[0], col + dire[1]
if x >= 0 and x < self.r and y >= 0 and y < self.c and matrix[x][y] == 0:
return True
return False
def dfs(self, matrix, row, col):
for dire in self.directions:
x, y = row + dire[0], col + dire[1]
if x < 0 or x >= self.r or y < 0 or y >= self.c:
continue
if matrix[x][y] > matrix[row][col] + 1:
matrix[x][y] = matrix[row][col] + 1
self.dfs(matrix, x, y)
# Runtime: 892 ms, faster than 28.14% of Python3 online submissions for 01 Matrix.
# Memory Usage: 16 MB, less than 16.67% of Python3 online submissions for 01 Matrix.
2. BFS
class Solution(object):
def updateMatrix(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[List[int]]
"""
if not matrix:
return matrix
r, c = len(matrix), len(matrix[0])
self.directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
queue = collections.deque()
for i in range(r):
for j in range(c):
if matrix[i][j] == 0:
queue.append((i, j))
else:
matrix[i][j] = float('inf')
while queue:
cur = queue.popleft()
for dire in self.directions:
x, y = cur[0] + dire[0], cur[1] + dire[1]
if x < 0 or x >= r or y < 0 or y >= c or matrix[x][y] <= matrix[cur[0]][cur[1]]:
continue
matrix[x][y] = matrix[cur[0]][cur[1]] + 1
queue.append((x, y))
return matrix
# Runtime: 972 ms, faster than 17.35% of Python3 online submissions for 01 Matrix.
# Memory Usage: 16.2 MB, less than 16.67% of Python3 online submissions for 01 Matrix.