Minimum distance to the end of a grid from source | Python3 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 ; 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
from collections import deque as queue NEW_LINE row = 5 NEW_LINE col = 5 NEW_LINE minDistance = [ [ 0 for i in range ( col + 1 ) ] for i in range ( row + 1 ) ] NEW_LINE visited = [ [ 0 for i in range ( col + 1 ) ] for i in range ( row + 1 ) ] NEW_LINE que = queue ( ) NEW_LINE def isValid ( grid , i , j ) : NEW_LINE INDENT if ( i < 0 or j < 0 or j >= col or i >= row or grid [ i ] [ j ] or visited [ i ] [ j ] ) : NEW_LINE INDENT return False NEW_LINE DEDENT return True NEW_LINE DEDENT def findMinPathminDistance ( grid , sourceRow , sourceCol ) : NEW_LINE INDENT if ( sourceCol == 0 or sourceCol == col - 1 or sourceRow == 0 or sourceRow == row - 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT minFromSource = row * col NEW_LINE for i in range ( row ) : NEW_LINE INDENT for j in range ( col ) : NEW_LINE INDENT minDistance [ i ] [ j ] = row * col NEW_LINE DEDENT DEDENT que . appendleft ( [ sourceRow , sourceCol ] ) NEW_LINE minDistance [ sourceRow ] [ sourceCol ] = 0 ; NEW_LINE visited [ sourceRow ] [ sourceCol ] = 1 ; NEW_LINE while ( len ( que ) > 0 ) : NEW_LINE INDENT cell = que . pop ( ) NEW_LINE cellRow = cell [ 0 ] NEW_LINE cellCol = cell [ 1 ] NEW_LINE if ( isValid ( grid , cellRow + 1 , cellCol ) ) : NEW_LINE INDENT que . appendleft ( [ cellRow + 1 , cellCol ] ) NEW_LINE minDistance [ cellRow + 1 ] [ cellCol ] = min ( minDistance [ cellRow + 1 ] [ cellCol ] , minDistance [ cellRow ] [ cellCol ] + 1 ) NEW_LINE visited [ cellRow + 1 ] [ cellCol ] = 1 NEW_LINE DEDENT if ( isValid ( grid , cellRow - 1 , cellCol ) ) : NEW_LINE INDENT que . appendleft ( [ cellRow - 1 , cellCol ] ) NEW_LINE minDistance [ cellRow - 1 ] [ cellCol ] = min ( minDistance [ cellRow - 1 ] [ cellCol ] , minDistance [ cellRow ] [ cellCol ] + 1 ) NEW_LINE visited [ cellRow - 1 ] [ cellCol ] = 1 NEW_LINE DEDENT if ( isValid ( grid , cellRow , cellCol + 1 ) ) : NEW_LINE INDENT que . appendleft ( [ cellRow , cellCol + 1 ] ) NEW_LINE minDistance [ cellRow ] [ cellCol + 1 ] = min ( minDistance [ cellRow ] [ cellCol + 1 ] , minDistance [ cellRow ] [ cellCol ] + 1 ) NEW_LINE visited [ cellRow ] [ cellCol + 1 ] = 1 ; NEW_LINE DEDENT if ( isValid ( grid , cellRow , cellCol - 1 ) ) : NEW_LINE INDENT que . appendleft ( [ cellRow , cellCol - 1 ] ) NEW_LINE minDistance [ cellRow ] [ cellCol - 1 ] = min ( minDistance [ cellRow ] [ cellCol - 1 ] , minDistance [ cellRow ] [ cellCol ] + 1 ) NEW_LINE visited [ cellRow ] [ cellCol - 1 ] = 1 NEW_LINE DEDENT DEDENT for i in range ( col ) : NEW_LINE INDENT minFromSource = min ( minFromSource , minDistance [ 0 ] [ i ] ) ; NEW_LINE DEDENT for i in range ( col ) : NEW_LINE INDENT minFromSource = min ( minFromSource , minDistance [ row - 1 ] [ i ] ) ; NEW_LINE DEDENT for i in range ( row ) : NEW_LINE INDENT minFromSource = min ( minFromSource , minDistance [ i ] [ 0 ] ) ; NEW_LINE DEDENT for i in range ( row ) : NEW_LINE INDENT minFromSource = min ( minFromSource , minDistance [ i ] [ col - 1 ] ) ; NEW_LINE DEDENT if ( minFromSource == row * col ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT return minFromSource NEW_LINE DEDENT sourceRow = 3 NEW_LINE sourceCol = 3 NEW_LINE 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 ] ] NEW_LINE print ( findMinPathminDistance ( grid , sourceRow , sourceCol ) ) NEW_LINE