Minimum distance to the end of a grid from source | C ++ implementation of the approach ; Global variables for grid , minDistance and visited array ; Queue for BFS ; Function to find whether the move is valid or not ; Function to return the minimum distance from source to the end of the grid ; If source is one of the destinations ; Set minimum value ; Precalculate minDistance of each grid with R * C ; Insert source position in queue ; Update minimum distance to visit source ; Set source to visited ; BFS approach for calculating the minDistance of each cell from source ; Iterate over all four cells adjacent to current cell ; Initialize position of current cell ; Cell below the current cell ; Push new cell to the queue ; Update one of its neightbor 's distance ; Above the current cell ; Right cell ; Left cell ; Pop the visited cell ; Minimum distance in the first row ; Minimum distance in the last row ; Minimum distance in the first column ; Minimum distance in the last column ; If no path exists ; Return the minimum distance ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define row  5 NEW_LINE #define col  5 NEW_LINE int minDistance [ row + 1 ] [ col + 1 ] , visited [ row + 1 ] [ col + 1 ] ; queue < pair < int , int > > que ; bool isValid ( int grid [ ] [ col ] , int i , int j ) { if ( i < 0 j < 0 j > = col i > = row grid [ i ] [ j ] visited [ i ] [ j ] ) return false ; return true ; } int findMinPathminDistance ( int grid [ ] [ col ] , int sourceRow , int sourceCol ) { if ( sourceCol == 0 sourceCol == col - 1 sourceRow == 0 sourceRow == row - 1 ) return 0 ; int minFromSource = row * col ; for ( int i = 0 ; i < row ; i ++ ) for ( int j = 0 ; j < col ; j ++ ) minDistance [ i ] [ j ] = row * col ; que . push ( make_pair ( sourceRow , sourceCol ) ) ; minDistance [ sourceRow ] [ sourceCol ] = 0 ; visited [ sourceRow ] [ sourceCol ] = 1 ; while ( ! que . empty ( ) ) { pair < int , int > cell = que . front ( ) ; int cellRow = cell . first ; int cellCol = cell . second ; if ( isValid ( grid , cellRow + 1 , cellCol ) ) { que . push ( make_pair ( cellRow + 1 , cellCol ) ) ; minDistance [ cellRow + 1 ] [ cellCol ] = min ( minDistance [ cellRow + 1 ] [ cellCol ] , minDistance [ cellRow ] [ cellCol ] + 1 ) ; visited [ cellRow + 1 ] [ cellCol ] = 1 ; } if ( isValid ( grid , cellRow - 1 , cellCol ) ) { que . push ( make_pair ( cellRow - 1 , cellCol ) ) ; minDistance [ cellRow - 1 ] [ cellCol ] = min ( minDistance [ cellRow - 1 ] [ cellCol ] , minDistance [ cellRow ] [ cellCol ] + 1 ) ; visited [ cellRow - 1 ] [ cellCol ] = 1 ; } if ( isValid ( grid , cellRow , cellCol + 1 ) ) { que . push ( make_pair ( cellRow , cellCol + 1 ) ) ; minDistance [ cellRow ] [ cellCol + 1 ] = min ( minDistance [ cellRow ] [ cellCol + 1 ] , minDistance [ cellRow ] [ cellCol ] + 1 ) ; visited [ cellRow ] [ cellCol + 1 ] = 1 ; } if ( isValid ( grid , cellRow , cellCol - 1 ) ) { que . push ( make_pair ( cellRow , cellCol - 1 ) ) ; minDistance [ cellRow ] [ cellCol - 1 ] = min ( minDistance [ cellRow ] [ cellCol - 1 ] , minDistance [ cellRow ] [ cellCol ] + 1 ) ; visited [ cellRow ] [ cellCol - 1 ] = 1 ; } que . pop ( ) ; } int i ; for ( i = 0 ; i < col ; i ++ ) minFromSource = min ( minFromSource , minDistance [ 0 ] [ i ] ) ; for ( i = 0 ; i < col ; i ++ ) minFromSource = min ( minFromSource , minDistance [ row - 1 ] [ i ] ) ; for ( i = 0 ; i < row ; i ++ ) minFromSource = min ( minFromSource , minDistance [ i ] [ 0 ] ) ; for ( i = 0 ; i < row ; i ++ ) minFromSource = min ( minFromSource , minDistance [ i ] [ col - 1 ] ) ; if ( minFromSource == row * col ) return -1 ; return minFromSource ; } int main ( ) { int sourceRow = 3 , sourceCol = 3 ; int grid [ row ] [ col ] = { 1 , 1 , 1 , 1 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 1 , 0 , 1 , 1 , 0 , 0 , 0 , 1 , 1 , 1 , 0 , 1 , 0 } ; cout << findMinPathminDistance ( grid , sourceRow , sourceCol ) ; return 0 ; }