Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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.
Frequently Asked Questions
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

Author 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:

Input Matrix 1

 

There exists two paths as following :

Paths output

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.

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.

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!

Thank you image

 

Previous article
Maximum Number of Edges that can be added to a tree so that it stays a Bipartite graph
Next article
Count the number of magical Indices in an array
Live masterclass