Graph: Given a matrix, find the distance of nearest cell having 0

Problem Statement:

You are given a binary matrix, you need to find the distance of the nearest 0 in the grid of each cell.

The distance is calculated as |n1 – n2| + |m1 – m2|, where n1, m1 are the row number and column number of the current cell, and n2, m2 are the row number and column number of the nearest cell having value 1.

Example:

Input: grid[][] = 
				[[1, 0, 1], 
                 [1, 1, 0], 
                 [1, 0, 0]]

Output:        [[0, 1, 0], 
                [0, 0, 1], 
                [0, 1, 2]]

grid [0][0] = 1, so nearest 1 is 0.
grid [0][1] = 0, so nearest 1 is 1 etc

Solution Explanation:

We will use multi source BFS approach to solve the problem.

Change all the non zero cells to infinity and update only non zero cells.

Direction vector will have the tuples representing 4 possible directions.

Time Complexity: O(rows * cols)
Space Complexity: O(rows * cols)

Code Solution

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;


vector<vector<int>> solution(vector<vector<int>>& mat) 
{
    int rows = mat.size();
    int cols = mat[0].size();

    // right, bottom, left, top - directions in which we can move
    vector<pair<int, int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    queue<pair<int, int>> q;

    for (int i = 0; i < rows; i++) 
    {
        for (int j = 0; j < cols; j++) 
        {
            if (mat[i][j] == 0) 
            {
                q.push({i, j});
            } 
            else 
            {
                mat[i][j] = INT_MAX;
            }
        }
    }

    while (!q.empty()) 
    {
        pair<int, int> cell = q.front();
        q.pop();
        int row = cell.first;
        int col = cell.second;

        for (pair<int, int> direction : directions) 
        {
            int newRow = row + direction.first;
            int newCol = col + direction.second;

            if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && mat[newRow][newCol] > mat[row][col] + 1) 
            {
                mat[newRow][newCol] = mat[row][col] + 1;
                q.push({newRow, newCol});
            }
        }
    }

    return mat;        
}

int main()
{
    vector<vector<int>>grid
    {
        {1, 0, 1},
        {1, 1, 0},
        {1, 0, 0}
    };
    
    vector<vector<int>> ans = solution(grid);
        
    for(auto i: ans)
    {
        for(auto j: i)
            cout << j << " ";
        cout << "\n";
    }
    
    return 0;
}

Output

1 0 1 
2 1 0 
1 0 0