Find Nearest 1 Distance in a Binary Matrix

Given a binary matrix of order m*n, the task is to find the distance of nearest 1 for each 0 in the matrix and print final distance matrix. From any cell (i,j), we can move only in four directions up, down, left and right.

Note: Distance from one cell to immediate another cell is always incremented by 1.

Examples:

Input :[[1,1,1],[1,0,1],[1,1,1]] 
Output :[[0, 0, 0], [0, 1, 0], [0, 0, 0]]

Input :[[1,0,1],[1,0,0],[1,0,1]]
Output :[[0, 1, 0], [0, 1, 1], [0, 1, 0]]

An efficient solution solution for this problem is to use BFS in python.

def nearestOne(matrix, n, m):
    # Distance matrix to store the distance of the nearest '1'
    dist = [[float('inf') for _ in range(n)] for _ in range(m)]
    
    # Arrays to determine the adjacent cells (up, down, left, right)
    newX = [-1, 0, 1, 0]
    newY = [0, -1, 0, 1]
    
    # Queue to store nodes for BFS
    q = []
    
    # Traverse the matrix and enqueue all cells containing '1'
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 1:
                # Distance of '1' from itself is always 0
                dist[i][j] = 0
                # Enqueue the cell coordinates
                q.append((i, j))
    
    # Perform BFS
    while q:
        # Dequeue the front element
        x, y = q.pop(0)
        
        # Check all adjacent cells
        for i in range(4):
            adjX, adjY = x + newX[i], y + newY[i]
            
            # If the new coordinates are within bounds and the distance can be minimized
            if 0 <= adjX < m and 0 <= adjY < n and dist[adjX][adjY] > dist[x][y] + 1:
                # Update the distance
                dist[adjX][adjY] = dist[x][y] + 1
                # Enqueue the adjacent cell
                q.append((adjX, adjY))
    
    return dist

if __name__ == "__main__":
    matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
    m, n = 3, 3
    result = nearestOne(matrix, n, m)
    # Print the distance matrix
    print(result)

Output:

[[0, 0, 0], [0, 1, 0], [0, 0, 0]]