题目
-
Given an
m x n
binary matrixmat
, return the distance of the nearest0
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 either0
or1
.- There is at least one
0
inmat
.
思路
bfs,以0号格为中心向四周扩展并更新距离值,由于是广度优先,遍历到的距离必定是最小的,不必为已遍历的格比大小。
动态规划,从左上角向右下角进行动态规划,再从右小角向左上角动态规划。
代码
python版本:
import queue
class Solution:
def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
distances = [[9999999 for _ in range(len(mat[0]))] for _ in range(len(mat))]
q = queue.Queue()
[q.put((i, j, 0,)) for i in range(len(mat)) for j in range(len(mat[i])) if mat[i][j] == 0]
while not q.empty():
i, j, dis = q.get()
if i<0 or i>=len(distances) or j<0 or j>=len(distances[0]) or distances[i][j]<=dis:
continue
distances[i][j] = dis
q.put((i, j+1, distances[i][j]+1,))
q.put((i, j-1, distances[i][j]+1,))
q.put((i+1, j, distances[i][j]+1,))
q.put((i-1, j, distances[i][j]+1,))
return distances
# 动态规划
class Solution:
def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
for i in range(len(mat)):
for j in range(len(mat[i])):
if mat[i][j] > 0:
up = mat[i-1][j] if i > 0 else math.inf
left = mat[i][j-1] if j > 0 else math.inf
mat[i][j] = min(up, left)+1
for i in range(len(mat)-1, -1, -1):
for j in range(len(mat[i])-1, -1, -1):
if mat[i][j] > 0:
down = mat[i+1][j] if i+1 < len(mat) else math.inf
right = mat[i][j+1] if j+1 < len(mat[i]) else math.inf
mat[i][j] = min(mat[i][j], down+1, right+1)
return mat