Intermediate Level
Implement the nearestZeroDistanceSum method that returns the sum of distances from every cell to its nearest zero.
You are given a binary matrix containing only 0 and 1. For every cell, determine the distance to the nearest cell containing 0.
Movement is allowed only in four directions. Return the sum of all nearest-zero distances in the matrix.
Example 1
Input
matrix (int[][]) =
[[0,0,0],[0,1,0],[1,1,1]]rows (int) =
3cols (int) =
3Returns (int)
5Example 2
Input
matrix (int[][]) =
[[0,1,1],[1,1,1],[1,1,0]]rows (int) =
3cols (int) =
3Returns (int)
10Example 3
Input
matrix (int[][]) =
[[0]]rows (int) =
1cols (int) =
1Returns (int)
0Use multi-source breadth-first search.
All zero cells are starting points with distance 0. Add them to the queue first. Then expand level by level into unvisited one-cells. The first time a cell is reached, it has the shortest distance to any zero.
Add each assigned distance to the answer.
Pseudocode:
function nearestZeroDistanceSum(matrix, rows, cols):
queue = all cells with value 0
distance = matrix filled with -1
set zero cells distance to 0
total = 0
while queue is not empty:
r, c = queue.popFront()
for each valid neighbor:
if distance[neighbor] == -1:
distance[neighbor] = distance[r][c] + 1
total = total + distance[neighbor]
queue.push(neighbor)
return totalReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run