Array Matrix Breadth First Search
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) = 3
cols (int) = 3
Return:
(int) 5
Example 2
Input:
matrix (int[][]) = [[0,1,1],[1,1,1],[1,1,0]]
rows (int) = 3
cols (int) = 3
Return:
(int) 10
Example 3
Input:
matrix (int[][]) = [[0]]
rows (int) = 1
cols (int) = 1
Return:
(int) 0

Use 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 total
Run your code to see the result.