Last Updated on December 13, 2022 by Prepbytes
CONCEPTS USED:
Recursion
DIFFICULTY LEVEL:
Easy
PROBLEM STATEMENT (SIMPLIFIED):
Rahul is stuck in a maze world, where the maze is a binary matrix of size NXM (each cell has value 0 or 1). To get out of this world he needs to calculate the distance to the nearest 1 for each cell in the maze. Distance between the two cells is calculated by |i1−i2|+|j1−j2|, where i1, j1 are the row number and column number of the current cell and i2, j2 are the row number and column number of the nearest cell having value 1.
See original problem statement here
For Example :
Input
2
3 3
0 0 1 1 1 1 1 0 1
4 4
1 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0
Output
1 1 0 0 0 0 0 1 0
0 1 0 1 1 2 1 2 1 1 1 2 0 0 0 1 OBSERVATION:
N=3 and M=3
Matrix =
[ 0 0 1 ]
[ 1 1 1 ]
[ 1 0 1 ]
Distance for index (0,0) to the nearest 1 is at index (1,0)
which is 1(1−0+0−0=1) so in distance matrix at index (0,0) input 1.
Distance matrix =
[ 1 1 0 ]
[ 0 0 0 ]
[ 0 1 0 ]SOLVING APPROACH:
A simple solution for this problem is to for each 0 in the matrix recursively check the nearest 1 in the matrix.
An efficient solution for this problem is to use BFS. Here is the algorithm to solve this problem
ALGO :
For our BFS routine, we keep a queue, q to maintain the queue of cells to be examined next.
We start by adding all the cells with 0s to q.
Intially, distance for each 0 cell is 0 and distance for each 1 is INT_MAX, which is updated during the BFS.
Pop the cell from queue, and examine its neighbours. If the new calculated distance for neighbour {i,j} is smaller, we add {i,j} to q and update dist[i][j].SOLUTIONS:
#include<bits/stdc++.h>
using namespace std;
class graph
{
private:
vector<int> g[10001];
int n,m;
public:
graph(int a, int b)
{
n = a;
m = b;
}
// Function to create graph with N*M nodes
// considering each cell as a node and each
// boundary as an edge.
void createGraph()
{
int k = 1; // A number to be assigned to a cell
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
// If last row, then add edge on right side.
if (i == n)
{
// If not bottom right cell.
if (j != m)
{
g[k].push_back(k+1);
g[k+1].push_back(k);
}
}
// If last column, then add edge toward down.
else if (j == m)
{
g[k].push_back(k+m);
g[k+m].push_back(k);
}
// Else make edge in all four direction.
else
{
g[k].push_back(k+1);
g[k+1].push_back(k);
g[k].push_back(k+m);
g[k+m].push_back(k);
}
k++;
}
}
}
// BFS function to find minimum distance
void bfs(bool visit[], int dist[], queue<int> q)
{
while (!q.empty())
{
int temp = q.front();
q.pop();
for (int i = 0; i < g[temp].size(); i++)
{
if (visit[g[temp][i]] != 1)
{
dist[g[temp][i]] =
min(dist[g[temp][i]], dist[temp]+1);
q.push(g[temp][i]);
visit[g[temp][i]] = 1;
}
}
}
}
// Printing the solution.
void print(int dist[])
{
for (int i = 1, c = 1; i <= n*m; i++, c++)
{
cout << dist[i] << " ";
}
cout<<endl;
}
};
int main()
{
int t;
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
bool mat[n][m];
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
cin>>mat[i][j];
}
graph g1(n, m);
g1.createGraph();
// To store minimum distance
int dist[10001];
// To mark each node as visited or not in BFS
bool visit[10001] = { 0 };
// Initialising the value of distance and visit.
for (int i = 1; i <= m*n; i++)
{
dist[i] = INT_MAX;
visit[i] = 0;
}
// Inserting nodes whose value in matrix
// is 1 in the queue.
int k = 1;
queue<int> q;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (mat[i][j] == 1)
{
dist[k] = 0;
visit[k] = 1;
q.push(k);
}
k++;
}
}
// Calling for Bfs with given Queue.
g1.bfs(visit, dist, q);
// Printing the solution.
g1.print(dist);
}
return 0;
}
Since, the new cells are added to the queue only if their current distance is greater than the calculated distance, cells are not likely to be added multiple times.
Space complexity:
O(r c). Additional O(r c)for queue.
[forminator_quiz id="2352"]
This article tried to discuss the concept of Recursion. Hope this blog helps you understand the concept. To practice more problems you can check out MYCODE | Competitive Programming.
please write the solution in java also.