PROBLEM STATEMENT:
You are given a binary matrix with n rows and m columns which is similar to a maze in real life. You are given a starting point and a end point. You can move in the cells where '1' is present, but not in the cells where '0' is present i.e. cells with '0' are blocked cells. You are to determine the shortest path between the starting point and the end point.
THINK
If can imagine it as a graph problem with connections between the cells with '1'. So, basically we can apply either DFS or BFS. But DFS may not always give us the shortest path, because in DFS, we explore every node completely to the dead end one by one and backtrack, but BFS will always give us the shortest path as we explore the nodes layer by layer and we consider all the possible paths and explore until we get the destination for the first time.
So, in this problem, we will apply BFS.
ANALYSIS:
In this problem, we can imagine all the cells as the vertex of the graph and all the adjacent relationships as the edges connecting the vertices.
APPROACH:
1. We start with the starting cell and apply BFS taking it as root node.
2. We take a two queues to store the x and y coordinates of the matrix, one queue for x coordinate and the other for y coordinate and initialize both with the x and y coordinate of starting cell (you can use only one queue if you want).
3. We also take a boolean array to track the already visited cells of the matrix (maze) and initially we mark them all of them as false, i.e. not visited
4. We take another boolean element referring if the destination cell is reached or not. We first initialize it as '0' or 'false'.
5. a) We loop the queues until both of them are not empty.
b) Dequeue the front cell from the queues ( Note that we have to dequeue both queues at the same time as we are taking two queues instead of one).
c) If we reach the destination coordinate i.e. the end point of the maze, then we return it.
d) In each step, we enqueue the previously not visited cells of the four adjacent cells and mark them as visited.
CODE:
#include <bits/stdc++.h>
using namespace std;
int r[]={-1,0,0,1};
int c[]={0,-1,1,0};
int BFS(int n, int m, bool *a,int x1, int y1, int x2, int y2)
{
//matrix to keep track of all visited cells
bool visited[n][m];
// initializing all the cells as non visited
memset(visited, false, sizeof(visited));
// queues for x and y coordinates seperately
queue<int>qx;
queue<int>qy;
//minimum distance from starting cell
queue<int>dist;
//mark starting cell as visited
visited[x1][y1]=true;
//enqueue starting cell coordinates
qx.push(x1);
qy.push(y1);
dist.push(0);
while(!qx.empty()&& !qy.empty())
{
//pop coordinates of front cell of the queue
int i=qx.front();
qx.pop();
int j=qy.front();
qy.pop();
int mindist=dist.front();
dist.pop();
if(i==x2 && j==y2)
{
return mindist;
break;
}
//check the possible cells that can be visited from the current cell
for(int k=0;k<4;k++)
{
if(i+r[k]>=0 && i+r[k]<n && j+c[k]>=0 && j+c[k]<m && *((a+(i+r[k])*m)+j+c[k])==true && !visited[i+r[k]][j+c[k]])
{
visited[i+r[k]][j+c[k]]=true;
qx.push(i+r[k]);
qy.push(j+c[k]);
dist.push(mindist+1);
}
}
}
//if there is no possible path
return -1;
}
int main()
{
int n,m;
cout<<"Enter matrix size"<<endl;
cin>>n>>m;
bool a[n][m];
cout<<"Enter the boolean matrix"<<endl;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
cin>>a[i][j];
}
cout<<"Enter starting coordinates and end address"<<endl;
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
int ans=BFS(n,m,(bool*)a,x1,y1,x2,y2);
if(ans==-1)
cout<<"NO PATH POSSIBLE"<<endl;
else
cout<<ans;
}
0 Comments