Given a N X N matrix (M) filled with 1 , 0 , 2 , 3 . Find the minimum numbers of moves needed to move from source to destination (sink) . while traversing through blank cells only. You can traverse up, down, right and left.
A value of cell 1 means Source.
A value of cell 2 means Destination.
A value of cell 3 means Blank cell.
A value of cell 0 means Blank Wall.
Note : there is only single source and single destination.they may be more than one path from source to destination(sink).each move in matrix we consider as ‘1’
Examples:
Input : M[3][3] = {{ 0 , 3 , 2 },
{ 3 , 3 , 0 },
{ 1 , 3 , 0 }};
Output : 4
Input : M[4][4] = {{ 3 , 3 , 1 , 0 },
{ 3 , 0 , 3 , 3 },
{ 2 , 3 , 0 , 3 },
{ 0 , 3 , 3 , 3 }};
Output : 4
Asked in: Adobe Interview
.
The idea is to use Level graph ( Breadth First Traversal ). Consider each cell as a node and each boundary between any two adjacent cells be an edge . so total number of Node is N*N.
1. Create an empty Graph having N*N node ( Vertex ).
2. Push all node into graph.
3. Note down source and sink vertices.
4. Now Apply level graph concept ( that we achieve using BFS ) .
In which we find level of every node from source vertex.
After that we return 'Level[d]' ( d is destination ).
(which is the minimum move from source to sink )
Below is implementation of above idea.
C++
// C++ program to find the minimum numbers // of moves needed to move from source to // destination . #include<bits/stdc++.h> using namespace std; #define N 4 class Graph { int V ; list < int > *adj; public : Graph( int V ) { this->V = V ; adj = new list<int>[V]; } void addEdge( int s , int d ) ; int BFS ( int s , int d) ; }; // add edge to graph void Graph :: addEdge ( int s , int d ) { adj[s].push_back(d); adj[d].push_back(s); } // Level BFS function to find minimum path // from source to sink int Graph :: BFS(int s, int d) { // Base case if (s == d) return 0; // make initial distance of all vertex -1 // from source int *level = new int[V]; for (int i = 0; i < V; i++) level[i] = -1 ; // Create a queue for BFS list<int> queue; // Mark the source node level[s] = '0' level[s] = 0 ; queue.push_back(s); // it will be used to get all adjacent // vertices of a vertex list<int>::iterator i; while (!queue.empty()) { // Dequeue a vertex from queue s = queue.front(); queue.pop_front(); // Get all adjacent vertices of the // dequeued vertex s. If a adjacent has // not been visited ( level[i] < '0') , // then update level[i] == parent_level[s] + 1 // and enqueue it for (i = adj[s].begin(); i != adj[s].end(); ++i) { // Else, continue to do BFS if (level[*i] < 0 || level[*i] > level[s] + 1 ) { level[*i] = level[s] + 1 ; queue.push_back(*i); } } } // return minimum moves from source to sink return level[d] ; } bool isSafe(int i, int j, int M[][N]) { if ((i < 0 || i >= N) || (j < 0 || j >= N ) || M[i][j] == 0) return false; return true; } // Returns minimum numbers of moves from a source (a // cell with value 1) to a destination (a cell with // value 2) int MinimumPath(int M[][N]) { int s , d ; // source and destination int V = N*N+2; Graph g(V); // create graph with n*n node // each cell consider as node int k = 1 ; // Number of current vertex for (int i =0 ; i < N ; i++) { for (int j = 0 ; j < N; j++) { if (M[i][j] != 0) { // connect all 4 adjacent cell to // current cell if ( isSafe ( i , j+1 , M ) ) g.addEdge ( k , k+1 ); if ( isSafe ( i , j-1 , M ) ) g.addEdge ( k , k-1 ); if (j< N-1 && isSafe ( i+1 , j , M ) ) g.addEdge ( k , k+N ); if ( i > 0 && isSafe ( i-1 , j , M ) ) g.addEdge ( k , k-N ); } // source index if( M[i][j] == 1 ) s = k ; // destination index if (M[i][j] == 2) d = k; k++; } } // find minimum moves return g.BFS (s, d) ; } // driver program to check above function int main() { int M[N][N] = {{ 3 , 3 , 1 , 0 }, { 3 , 0 , 3 , 3 }, { 2 , 3 , 0 , 3 }, { 0 , 3 , 3 , 3 } }; cout << MinimumPath(M) << endl; return 0; } |
Python3
# Python3 program to find the minimum numbers # of moves needed to move from source to # destination . class Graph: def __init__(self, V): self.V = V self.adj = [[] for i in range(V)] # add edge to graph def addEdge (self, s , d ): self.adj[s].append(d) self.adj[d].append(s) # Level BFS function to find minimum # path from source to sink def BFS(self, s, d): # Base case if (s == d): return 0 # make initial distance of all # vertex -1 from source level = [-1] * self.V # Create a queue for BFS queue = [] # Mark the source node level[s] = '0' level[s] = 0 queue.append(s) # it will be used to get all adjacent # vertices of a vertex while (len(queue) != 0): # Dequeue a vertex from queue s = queue.pop() # Get all adjacent vertices of the # dequeued vertex s. If a adjacent has # not been visited ( level[i] < '0') , # then update level[i] == parent_level[s] + 1 # and enqueue it i = 0 while i < len(self.adj[s]): # Else, continue to do BFS if (level[self.adj[s][i]] < 0 or level[self.adj[s][i]] > level[s] + 1 ): level[self.adj[s][i]] = level[s] + 1 queue.append(self.adj[s][i]) i += 1 # return minimum moves from source # to sink return level[d] def isSafe(i, j, M): global N if ((i < 0 or i >= N) or (j < 0 or j >= N ) or M[i][j] == 0): return False return True # Returns minimum numbers of moves from a # source (a cell with value 1) to a destination # (a cell with value 2) def MinimumPath(M): global N 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 (M[i][j] != 0): # connect all 4 adjacent cell to # current cell if (isSafe (i , j + 1 , M)): g.addEdge (k , k + 1) if (isSafe (i , j - 1 , M)): g.addEdge (k , k - 1) if (j < N - 1 and isSafe (i + 1 , j , M)): g.addEdge (k , k + N) if (i > 0 and isSafe (i - 1 , j , M)): g.addEdge (k , k - N) # source index if(M[i][j] == 1): s = k # destination index if (M[i][j] == 2): d = k k += 1 # find minimum moves return g.BFS (s, d) # Driver Code N = 4M = [[3 , 3 , 1 , 0 ], [3 , 0 , 3 , 3 ], [2 , 3 , 0 , 3 ], [0 , 3 , 3 , 3]] print(MinimumPath(M)) # This code is contributed by PranchalK |
Output:
4
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments