Minimum distance to the end of a grid from source | Java implementation of the approach ; Pair class ; 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 ; add 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
import java . util . * ; class GFG { static class Pair { int first , second ; Pair ( int a , int b ) { first = a ; second = b ; } } static int row = 5 ; static int col = 5 ; static int minDistance [ ] [ ] = new int [ row + 1 ] [ col + 1 ] , visited [ ] [ ] = new int [ row + 1 ] [ col + 1 ] ; static Queue < Pair > que = new LinkedList < > ( ) ; static boolean isValid ( int grid [ ] [ ] , int i , int j ) { if ( i < 0 j < 0 j >= col i >= row grid [ i ] [ j ] != 0 visited [ i ] [ j ] != 0 ) return false ; return true ; } static int findMinPathminDistance ( int grid [ ] [ ] , 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 . add ( new Pair ( sourceRow , sourceCol ) ) ; minDistance [ sourceRow ] [ sourceCol ] = 0 ; visited [ sourceRow ] [ sourceCol ] = 1 ; while ( que . size ( ) > 0 ) { Pair cell = que . peek ( ) ; int cellRow = cell . first ; int cellCol = cell . second ; if ( isValid ( grid , cellRow + 1 , cellCol ) ) { que . add ( new Pair ( cellRow + 1 , cellCol ) ) ; minDistance [ cellRow + 1 ] [ cellCol ] = Math . min ( minDistance [ cellRow + 1 ] [ cellCol ] , minDistance [ cellRow ] [ cellCol ] + 1 ) ; visited [ cellRow + 1 ] [ cellCol ] = 1 ; } if ( isValid ( grid , cellRow - 1 , cellCol ) ) { que . add ( new Pair ( cellRow - 1 , cellCol ) ) ; minDistance [ cellRow - 1 ] [ cellCol ] = Math . min ( minDistance [ cellRow - 1 ] [ cellCol ] , minDistance [ cellRow ] [ cellCol ] + 1 ) ; visited [ cellRow - 1 ] [ cellCol ] = 1 ; } if ( isValid ( grid , cellRow , cellCol + 1 ) ) { que . add ( new Pair ( cellRow , cellCol + 1 ) ) ; minDistance [ cellRow ] [ cellCol + 1 ] = Math . min ( minDistance [ cellRow ] [ cellCol + 1 ] , minDistance [ cellRow ] [ cellCol ] + 1 ) ; visited [ cellRow ] [ cellCol + 1 ] = 1 ; } if ( isValid ( grid , cellRow , cellCol - 1 ) ) { que . add ( new Pair ( cellRow , cellCol - 1 ) ) ; minDistance [ cellRow ] [ cellCol - 1 ] = Math . min ( minDistance [ cellRow ] [ cellCol - 1 ] , minDistance [ cellRow ] [ cellCol ] + 1 ) ; visited [ cellRow ] [ cellCol - 1 ] = 1 ; } que . remove ( ) ; } int i ; for ( i = 0 ; i < col ; i ++ ) minFromSource = Math . min ( minFromSource , minDistance [ 0 ] [ i ] ) ; for ( i = 0 ; i < col ; i ++ ) minFromSource = Math . min ( minFromSource , minDistance [ row - 1 ] [ i ] ) ; for ( i = 0 ; i < row ; i ++ ) minFromSource = Math . min ( minFromSource , minDistance [ i ] [ 0 ] ) ; for ( i = 0 ; i < row ; i ++ ) minFromSource = Math . min ( minFromSource , minDistance [ i ] [ col - 1 ] ) ; if ( minFromSource == row * col ) return - 1 ; return minFromSource ; } public static void main ( String args [ ] ) { int sourceRow = 3 , sourceCol = 3 ; int grid [ ] [ ] = { { 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 } } ; System . out . println ( findMinPathminDistance ( grid , sourceRow , sourceCol ) ) ; } }