Given a N X N matrix (M) with the values 0, 1, 2, and 3. Determine the smallest number of movements required to go from source cell to destination cell while simply passing through blank cells only. You may go up, down, right, and left.
The cell with the value “1” value denotes the source.
The Cell with the value “2” value denotes the destination.
The Cell with the value “3” value denotes the blank cell.
The Cell with the value “0” value denotes the blank wall.
Note: There will only be one source and one destination. There can be more than one path from source to destination, return the shortest path length.
Example
Consider the following 4 x 4 matrix:
There exists two paths as following :
The minimum path length is 4. Therefore we will return 4.
Input-Output
We have an N x N matrix.
Example 1
Input
[ [0 , 3 , 2 ]
[3, 3, 0]
[1 , 3 , 0] ]
Output
4
Example 2
Input
[ [3 , 3 , 1 , 0]
[3 , 0 , 3 , 3]
[2 , 3 , 0 , 3]
[0 , 3 , 3 , 3] ]
Output
4
Approach - BFS
The approach is to use a Breadth First Traversal. Consider each cell a node, with any border between two adjacent cells acting as an edge. As a result, the total number of Nodes is N*N.
Follow the below algorithm:
Make an empty Graph with N*N nodes ( Vertex ).
Convert all nodes into a graph.
Make a note of the source and sink vertices.
Now Use the level graph idea ( that we achieve using BFS). We determine each node's level starting from the source vertex. Following that, we return to the level of destination, which is the shortest distance from source to sink.
C++ Code
#include<bits/stdc++.h>
using namespace std;
class Graph
{
int V ;
list < int > *adj;
public :
Graph( int V )
{
this->V = V ;
adj = new list<int>[V];
}
// function to add edge
void addEdge( int s , int d ){
adj[s].push_back(d);
adj[d].push_back(s);
}
// BFS function to find minimum path from source to destination
int BFS ( int s , int d){
// Base case if destination reached.
if (s == d)
return 0;
// mark distance of all the nodes as -1.
int *dist = new int[this->V];
for (int i = 0; i < V; i++)
dist[i] = -1 ;
//queue for BFS
list<int> queue;
// distance of source node as 0
dist[s] = 0 ;
//add source to queue
queue.push_back(s);
while (!queue.empty())
{
// Dequeue a vertex from queue
s = queue.front();
queue.pop_front();
// Get the vertices that are next to the dequeued vertex s.
//If a neighbor has not been visited (dist[i] < '0'),
//update dist[i] == parent_dist[s] + 1 and enqueue it.
for (auto i = adj[s].begin(); i != adj[s].end(); ++i)
{
if (dist[*i] < 0 || dist[*i] > dist[s] + 1 )
{
dist[*i] = dist[s] + 1 ;
queue.push_back(*i);
}
}
}
// return minimum moves
return dist[d] ;
}
};
bool isPossible(int i, int j, vector<vector<int>> matrix)
{
int N=matrix.size();
if ((i < 0 || i >= N) ||
(j < 0 || j >= N ) || matrix[i][j] == 0)
return false;
return true;
}
// Function that Returns minimum numbers of moves required from the source
// to destination
int MinPath(vector<vector<int>> matrix)
{
int N=matrix.size();
int s , d ; // source and destination nodes
int V = N*N+2;
Graph g(V);
int k = 1 ;
for (int i =0 ; i < N ; i++)
{
for (int j = 0 ; j < N; j++)
{
if (matrix[i][j] != 0)
{
// connect all 4 adjacent cell to
// current cell
if ( isPossible ( i , j+1 , matrix ) )
g.addEdge ( k , k+1 );
if ( isPossible ( i , j-1 , matrix ) )
g.addEdge ( k , k-1 );
if (j< N-1 && isPossible ( i+1 , j , matrix ) )
g.addEdge ( k , k+N );
if ( i > 0 && isPossible ( i-1 , j , matrix ) )
g.addEdge ( k , k-N );
}
// source index
if( matrix[i][j] == 1 )
s = k ;
// destination index
if (matrix[i][j] == 2)
d = k;
k++;
}
}
// find minimum moves
return g.BFS (s, d);
}
// driver program to check above function
int main()
{
vector<vector<int>> matrix = {{ 3 , 3 , 1 , 0 },
{ 3 , 0 , 3 , 3 },
{ 2 , 3 , 0 , 3 },
{ 0 , 3 , 3 , 3 }
};
cout << MinPath(matrix) << endl;
return 0;
}
Output
4
Python Code
class Graph:
def __init__(self, V):
self.V = V
self.adj = [[] for i in range(V)]
# function to add edge
def addEdge (self, s , d ):
self.adj[s].append(d)
self.adj[d].append(s)
# BFS function to find minimum path from source to destination
def BFS(self, s, d):
# Base case if destination reached.
if (s == d):
return 0
# mark distance of all the nodes as -1.
dist = [-1] * self.V
# queue for BFS
queue = []
# distance of source node as 0
dist[s] = 0
# add source to queue
queue.append(s)
while (len(queue) != 0):
# Dequeue a vertex from queue
s = queue.pop()
# Get the vertices that are next to the dequeued vertex s.
# If a neighbor has not been visited (dist[i] < '0'),
# update dist[i] == parent_dist[s] + 1 and enqueue it.
i = 0
while i < len(self.adj[s]):
# Else, continue to do BFS
if (dist[self.adj[s][i]] < 0 or
dist[self.adj[s][i]] > dist[s] + 1 ):
dist[self.adj[s][i]] = dist[s] + 1
queue.append(self.adj[s][i])
i += 1
# return minimum moves from source
# to sink
return dist[d]
def isPossible(i, j, matrix):
N=len(matrix)
if ((i < 0 or i >= N) or
(j < 0 or j >= N ) or matrix[i][j] == 0):
return False
return True
# Function that Returns minimum numbers of
# moves required from the source to destination
def MinPath(matrix):
N=len(matrix)
s , d = None, None # source and destination
V = N * N + 2
g = Graph(V)
# create graph with n*n node
# each cell consider as node
k = 1 # Number of current vertex
for i in range(N):
for j in range(N):
if (matrix[i][j] != 0):
# connect all 4 adjacent cell to
# current cell
if (isPossible (i , j + 1 , matrix)):
g.addEdge (k , k + 1)
if (isPossible (i , j - 1 , matrix)):
g.addEdge (k , k - 1)
if (j < N - 1 and isPossible (i + 1 , j , matrix)):
g.addEdge (k , k + N)
if (i > 0 and isPossible (i - 1 , j , matrix)):
g.addEdge (k , k - N)
# source node
if(matrix[i][j] == 1):
s = k
# destination node
if (matrix[i][j] == 2):
d = k
k += 1
# return minimum moves
return g.BFS (s, d)
# Driver Code
matrix = [[3 , 3 , 1 , 0 ], [3 , 0 , 3 , 3 ],
[2 , 3 , 0 , 3 ], [0 , 3 , 3 , 3]]
print(MinPath(matrix))
Output
4
Complexity Analysis
Time Complexity - O(N x N)
We had to iterate over all the nodes at most once, and the number of nodes is NxN.
Space Complexity - O(N*N)
We need to create a graph of NxN vertices.
Frequently Asked Questions
How can we represent a Graph?
There are two ways to represent a Graph:
1. Adjacency Matrix
2. Adjacency List
What are the primary elements of a graph?
The primary elements of a graph are the vertices and the edges. The vertices represent the particular things being linked, while the edges reflect the interactions between those objects.
What is the difference between a directed and undirected graph?
A directed graph is one in which the edges are assigned a specified direction. As a result, the edges can only be traveled in one way. On the other hand, an undirected graph has no direction associated with its edges, allowing them to be traversed in any way.
Conclusion
We hope this blog has helped you enhance your Knowledge about Graphs. We discussed a problem in finding a Minimum number of moves needed to move from one cell of the matrix to another. Then we write code in two different languages - C++ and Python for better understanding.
You can also refer to our Guided Path on Coding Ninjas Studio to upskill yourself in domains like Data Structures and Algorithms, Competitive Programming, Aptitude, and many more! You can also prepare for tech giants companies like Amazon, Microsoft, Uber, etc., by looking for the questions asked by them in recent interviews. If you want to prepare for placements, refer to the interview bundle. If you are nervous about your interviews, you can see interview experiences to get ideas about these companies' questions.
Nevertheless, you may consider our premium courses to give your career an edge over others!
Do upvote our blogs if you find them helpful and engaging!
46+ registered 