# Shortest Source to Destination Path

In this article, we are going to see how to find the shortest path from source to destination in a 2D maze? This problem has been featured in the coding round of Samsung.
Submitted by Radib Kar, on December 28, 2018

Problem statement:

Given a Boolean 2D matrix (0-based index), find whether there is a path from (0,0) to (x,y) and if there is one path, print the minimum no of steps needed to reach it, else print -1 if the destination is not reachable. Moves are possible in only four directions i.e. up, down, left and right. The path can only be created out of a cell if its value is 1.

Example:

```    Matrix dimension: 3X3
Matrix:
1 0 0
1 1 0
0 1 1
Destination point: (2, 2)
Shortest path length to reach destination: 4
```

Solution

Pre-requisites:

1. Defining a point in the maze

We need to define a "point" class having two data attributes 1) row no and 2) column no

```class point{
public:
int row;
int column;
};
```

2. Defining node used in solution

A concept of node is used in the solution which actually is an object with two data attributes

1. A point
2. Distance of the point from the source, distance is calculated by path traversed
```class node{
public:
point p;
int d;
};
```

Algorithm:

1. Start from the source node. (point (0,0) with a distance 0 )
2. Declare a queue for BFS traversal.
3. Check whether a path from the current node is possible or not.
4. If possible
Mark the node visited.
EnQueue its neighbour nodes if unvisited
5. Check for final node to be reached.
6. In case of traversing to the neighbour nodes increment node data distance by 1.
7. Return the final node distance value when final node is reached.
8. If all nodes are processed to make the queue empty, then it isn't possible to be reached
Print -1.

Since we have use BFS traversal technique it's guaranteed to reach the destination node in minimum no of steps if the destination is reachable from the source node. (point (0, 0)).

So the steps are:

1. Checking the base cases
Check whether point (0,0) is 0 or not.
If it's 0, then we can't make any path from here, so to print -1 & return.
2. Initialize Mark[row][col] = false
Initially all nodes are unvisited
3. Initialize the queue q
4. Create source node & EnQueue(q, source node).
5. Start traversal
6. ```While (queue is not empty)
Temp=DeQueue(q)
IF temp==destination node
printnode distanceand return
END IF
For all neighbour nodes //increment distance by 1
Check whether valid node && unvisited
IFit's a valid node && unvisited
EnQueue(neighbour node, q)
Mark neighbour node visited
END IF
END FOR
END WHILE
```
7. If control comes out of the loop that means destination can't be reached, thus print -1.

Finding neighbour nodes

All the directions are marked on basis of the current index.

• For rightward neighbour-> (row, column+1)
• For downward neighbour-> (row+1, column)
• For leftward neighbour -> (row, column-1)
• For upward neighbour-> (row-1, column)

Checking valid node

```If (row of current point<0)
Out of matrix;
If (column of current point<0)
Out of matrix;
If (row of current point>=m) //m is row no of matrix
Out of matrix;
If (column of current point>=n) //n is column no of matrix
Out of matrix;
```

### C++ implementation

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

//checking valid node
int isvalid(int nextx,int nexty,int m,int n){
if(nextx>=0 && nextx<m && nexty>=0 && nexty<n)
return 1;
return 0;
}

//defining point
class point{
public:
int row;
int col;
//make point
void mpoint(int m,int n){
row=m;
col=n;
}
};

//defining node
class node{
public:
point p;
int d;
void mnode(point q,int dis){ //make node
p.row=q.row;
p.col=q.col;
d=dis;
}
};

//finding shortest path
int shortest(int** a,int m,int n,int x1,int y1){
if(a[0][0]==0)//base case
return -1;

bool visited[m][n];
//initialize
memset(visited,false,sizeof(visited));

//declare queue by STL
queue<node> q;

point curr;
//set the source point (0,0)
curr.mpoint(0,0);

node t;
//set the source node at point (0,0)
t.mnode(curr,0);

//ENQUEUE source node
q.push(t);

//direction matrices
int arrx[]={-1,0,1,0};
int arry[]={0,1,0,-1};

point c;
node v;
while(!q.empty()){
//DEQUEUE
v=q.front();

c=v.p;
//if destnation node is reached
if(x1==c.row && y1==c.col ){
return v.d;
}
q.pop();
//check for all four neighbours
for(int i=0;i<4;i++){
int nextx=c.row+arrx[i];
int nexty=c.col+arry[i];
//if valid node && not visited yet
if(isvalid(nextx,nexty,m,n) && a[nextx][nexty] && !visited[nextx][nexty]){
curr.mpoint(nextx,nexty);
//set neighbour node by incrementing distance value
t.mnode(curr,(v.d)+1);
q.push(t); //EnQueue
//mark as visited
visited[nextx][nexty]=true;
}
}
}
return -1;
}

int main()
{
int m,n,x,y;

cout<<"enter matrix row & column"<<endl;
scanf("%d %d",&m,&n);

int **a=(int**)malloc(sizeof(int*)*m);

for(int i=0;i<m;i++)
a[i]=(int*)(malloc(sizeof(int)*n));

cout<<"enter matrix elements (0/1)"<<endl;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
scanf("%d",&a[i][j]);

cout<<"enter row & column of destinanation point"<<endl;
scanf("%d %d",&x,&y);

if(shortest(a,m,n,x,y)!=-1)//if path found
printf("shortest distance is %d\n",shortest(a,m,n,x,y));
else{
cout<<-1<<endl;
cout<<"no path found\n";
}

return 0;
}
```

Output

```First run:
enter matrix row & column
3 3
enter matrix elements (0/1)
1 0 0
1 1 0
0 1 1
enter row & column of destinanation point
2 2
shortest distance is 4

Second run:
enter matrix row & column
4 4
enter matrix elements (0/1)
1 0 1 0
0 0 0 1
1 1 1 1
0 1 1 0
enter row & column of destinanation point
2 3
-1
no path found
```

Recommended posts

What's New (MCQs)

Top Interview Coding Problems/Challenges!

IncludeHelp's Blogs

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates