1.
Introduction
2.
Example
3.
Input-Output
3.1.
Example 1
3.2.
Example 2
4.
Approach - BFS
4.1.
C++ Code
4.2.
Python Code
5.
Complexity Analysis
6.
6.1.
How can we represent a Graph?
6.2.
What are the primary elements of a graph?
6.3.
What is the difference between a directed and undirected graph?
7.
Conclusion
Last Updated: Mar 27, 2024

# Minimum number of moves needed to move from one cell of the matrix to another

Rhythm Jain
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

## Introduction

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Input-Output

We have an N x N matrix.

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.

• 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 ;

public :
Graph( int V )
{
this->V = V ;
}

void addEdge( int s , int d ){
}

// 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 ;

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.
{

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)]

def addEdge (self, s , d ):

# 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

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

# Else, continue to do BFS
dist[self.adj[s][i]] > dist[s] + 1 ):
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.

### How can we represent a Graph?

There are two ways to represent a Graph:

### 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.

See Basics of C++ with Data StructureDBMSOperating System by Coding Ninjas, and keep practicing on our platform Coding Ninjas Studio.

If you think you are ready for the tech giants company, check out the mock test series on code studio.

Check out this problem - Matrix Median

You can also refer to our Guided Path on Coding Ninjas Studio to upskill yourself in domains like Data Structures and AlgorithmsCompetitive ProgrammingAptitude, 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!

Happy Learning!

Live masterclass