01 Matrix

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.

Example 1:

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

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

Approach

Java

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Matrix01 {
    public static void main(String[] args) {
        int[][] matrix = { { 0, 0, 0 }, { 0, 1, 0 }, { 1, 1, 1 } };;
        updateMatrix(matrix);
        for (int i = 0; i < matrix.length; i++) {
            System.out.println(Arrays.toString(matrix[i]));
        }
    }

    static public int[][] updateMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    queue.offer(new int[] { i, j });
                } else {
                    matrix[i][j] = Integer.MAX_VALUE;
                }
            }
        }

        int[][] dirs = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            for (int[] d : dirs) {
                int r = cell[0] + d[0];
                int c = cell[1] + d[1];
                if (r < 0 || r >= m || c < 0 || c >= n || 
                matrix[r][c] <= matrix[cell[0]][cell[1]] + 1) {
                    continue;
                }

                queue.add(new int[] { r, c });
                matrix[r][c] = matrix[cell[0]][cell[1]] + 1;
            }
        }

        return matrix;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

//function to check if current cell is valid
//or not
bool isSafe(vector<vector<int>> &matrix,int i,int j)
{
        int n=matrix.size();
        int m=matrix[0].size();
        return (i>=0 &&i<n)&&(j>=0&&j<m)&&(matrix[i][j]==0||matrix[i][j]==1);
        
}

//bfs funtion 
int bfs(vector<vector<int>>&matrix,int x,int y,int n)
{
        queue<pair<int,int>>q;
        q.push({x,y});
        int res=0;
        while(!q.empty())
        {
            int len=q.size();
            while(len--)
            {
                auto it=q.front();
                q.pop();
                int x=it.first;
                int y=it.second;
                if(matrix[x][y]==0)
                      return res;
                else
                {
                    if(isSafe(matrix,x,y+1))
                          q.push({x,y+1});
                    if(isSafe(matrix,x,y-1))
                          q.push({x,y-1});
                    if(isSafe(matrix,x+1,y))
                          q.push({x+1,y});
                    if(isSafe(matrix,x-1,y))
                          q.push({x-1,y});
                }
               
            }
             res++;
        }
        return res;
}

//function  to update the matrix
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) 
{
       int n=matrix.size();
       int m=matrix[0].size();
        vector<vector<int>> res=matrix;
       for(int i=0;i<n;i++)
       {
           for(int j=0;j<m;j++)
           {
               if(res[i][j]==0)
                      continue;
              else
                   res[i][j]=bfs(matrix,i,j,n);
           }
       }
        return res;
}
int main()
{
 vector<vector<int>> matrix={{0,0,0},
                             {0,1,0},
                             {1,1,1}};
  matrix=updateMatrix(matrix);
  cout<<"[";
  for(int i=0;i<matrix.size();i++)
    {
         cout<<"[";
        for(int j=0;j<matrix[i].size();j++)
          {
              if(j!=matrix[i].size()-1)
                cout<<matrix[i][j]<<",";
              else
                cout<<matrix[i][j];
              
          }
          if(i!=matrix.size()-1)
             cout<<"],\n";
          else
           cout<<"]";
    }
    cout<<"]";
}