Find the minimum number of moves needed to move from one cell of matrix to another | C ++ program to find the minimum numbers of moves needed to move from source to destination . ; add edge to graph ; Level BFS function to find minimum path from source to sink ; Base case ; make initial distance of all vertex - 1 from source ; Create a queue for BFS ; Mark the source node level [ s ] = '0' ; it will be used to get all adjacent vertices of a vertex ; Dequeue a vertex from queue ; 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 ; Else , continue to do BFS ; return minimum moves from source to sink ; Returns minimum numbers of moves from a source ( acell with value 1 ) to a destination ( a cell withvalue 2 ) ;  ; create graph with n * n node each cell consider as node Number of current vertex ; connect all 4 adjacent cell to current cell ; source index ; destination index ; find minimum moves ; driver program to check above function
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  4 NEW_LINE 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 ) ; } ; void Graph :: addEdge ( int s , int d ) { adj [ s ] . push_back ( d ) ; adj [ d ] . push_back ( s ) ; } int Graph :: BFS ( int s , int d ) { if ( s == d ) return 0 ; int * level = new int [ V ] ; for ( int i = 0 ; i < V ; i ++ ) level [ i ] = -1 ; list < int > queue ; level [ s ] = 0 ; queue . push_back ( s ) ; list < int > :: iterator i ; while ( ! queue . empty ( ) ) { s = queue . front ( ) ; queue . pop_front ( ) ; for ( i = adj [ s ] . begin ( ) ; i != adj [ s ] . end ( ) ; ++ i ) { if ( level [ * i ] < 0 level [ * i ] > level [ s ] + 1 ) { level [ * i ] = level [ s ] + 1 ; queue . push_back ( * i ) ; } } } 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 ; } int MinimumPath ( int M [ ] [ N ] ) { int s , d ; 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 ( M [ i ] [ j ] != 0 ) { 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 ) ; } if ( M [ i ] [ j ] == 1 ) s = k ; if ( M [ i ] [ j ] == 2 ) d = k ; k ++ ; } } return g . BFS ( s , d ) ; } 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 ; }