Minimum distance to the end of a grid from source | 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
class Pair { constructor ( a , b ) { this . first = a ; this . second = b ; } } let row = 5 ; let col = 5 ; let minDistance = new Array ( row + 1 ) ; for ( let i = 0 ; i < row + 1 ; i ++ ) { minDistance [ i ] = new Array ( col + 1 ) ; for ( let j = 0 ; j < col + 1 ; j ++ ) minDistance [ i ] [ j ] = 0 ; } let visited = new Array ( row + 1 ) ; for ( let i = 0 ; i < row + 1 ; i ++ ) { visited [ i ] = new Array ( col + 1 ) ; for ( let j = 0 ; j < col + 1 ; j ++ ) visited [ i ] [ j ] = 0 ; } let que = [ ] ; function isValid ( grid , i , j ) { if ( i < 0 j < 0 j >= col i >= row grid [ i ] [ j ] != 0 visited [ i ] [ j ] != 0 ) return false ; return true ; } function findMinPathminDistance ( grid , sourceRow , sourceCol ) { if ( sourceCol == 0 sourceCol == col - 1 sourceRow == 0 sourceRow == row - 1 ) return 0 ; let minFromSource = row * col ; for ( let i = 0 ; i < row ; i ++ ) for ( let j = 0 ; j < col ; j ++ ) minDistance [ i ] [ j ] = row * col ; que . push ( new Pair ( sourceRow , sourceCol ) ) ; minDistance [ sourceRow ] [ sourceCol ] = 0 ; visited [ sourceRow ] [ sourceCol ] = 1 ; while ( que . length > 0 ) { let cell = que [ 0 ] ; let cellRow = cell . first ; let cellCol = cell . second ; if ( isValid ( grid , cellRow + 1 , cellCol ) ) { que . push ( 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 . push ( 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 . push ( 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 . push ( 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 . shift ( ) ; } let 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 ; } let sourceRow = 3 , sourceCol = 3 ; let 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 ] ] ; document . write ( findMinPathminDistance ( grid , sourceRow , sourceCol ) ) ;