Minimum steps to reach any of the boundary edges of a matrix | Set 1 | Python program to find Minimum steps to reach any of the boundary edges of a matrix ; Function to find out minimum steps ; boundary edges reached ; already had a route through this point , hence no need to re - visit ; visiting a position ; vertically up ; horizontally right ; horizontally left ; vertically down ; minimum of every path ; Function that returns the minimum steps ; index to store the location at which you are standing ; find '2' in the matrix ; Initialize dp matrix with - 1 ; Initialize vis matrix with false ; Call function to find out minimum steps using memoization and recursion ; if not possible ; Driver Code
r = 4 NEW_LINE col = 5 NEW_LINE def findMinSteps ( mat , n , m , dp , vis ) : NEW_LINE INDENT if ( n == 0 or m == 0 or n == ( r - 1 ) or m == ( col - 1 ) ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( dp [ n ] [ m ] != - 1 ) : NEW_LINE INDENT return dp [ n ] [ m ] NEW_LINE DEDENT vis [ n ] [ m ] = True NEW_LINE ans1 , ans2 , ans3 , ans4 = 10 ** 9 , 10 ** 9 , 10 ** 9 , 10 ** 9 NEW_LINE if ( mat [ n - 1 ] [ m ] == 0 ) : NEW_LINE INDENT if ( vis [ n - 1 ] [ m ] == False ) : NEW_LINE INDENT ans1 = 1 + findMinSteps ( mat , n - 1 , m , dp , vis ) NEW_LINE DEDENT DEDENT if ( mat [ n ] [ m + 1 ] == 0 ) : NEW_LINE INDENT if ( vis [ n ] [ m + 1 ] == False ) : NEW_LINE INDENT ans2 = 1 + findMinSteps ( mat , n , m + 1 , dp , vis ) NEW_LINE DEDENT DEDENT if ( mat [ n ] [ m - 1 ] == 0 ) : NEW_LINE INDENT if ( vis [ n ] [ m - 1 ] == False ) : NEW_LINE INDENT ans3 = 1 + findMinSteps ( mat , n , m - 1 , dp , vis ) NEW_LINE DEDENT DEDENT if ( mat [ n + 1 ] [ m ] == 0 ) : NEW_LINE INDENT if ( vis [ n + 1 ] [ m ] == False ) : NEW_LINE INDENT ans4 = 1 + findMinSteps ( mat , n + 1 , m , dp , vis ) NEW_LINE DEDENT DEDENT dp [ n ] [ m ] = min ( ans1 , min ( ans2 , min ( ans3 , ans4 ) ) ) NEW_LINE return dp [ n ] [ m ] NEW_LINE DEDENT def minimumSteps ( mat , n , m ) : NEW_LINE INDENT twox = - 1 NEW_LINE twoy = - 1 NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( m ) : NEW_LINE INDENT if ( mat [ i ] [ j ] == 2 ) : NEW_LINE INDENT twox = i NEW_LINE twoy = j NEW_LINE break NEW_LINE DEDENT DEDENT if ( twox != - 1 ) : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT dp = [ [ - 1 for i in range ( col ) ] for i in range ( r ) ] NEW_LINE vis = [ [ False for i in range ( col ) ] for i in range ( r ) ] NEW_LINE res = findMinSteps ( mat , twox , twoy , dp , vis ) NEW_LINE if ( res >= 10 ** 9 ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT else : NEW_LINE INDENT return res NEW_LINE DEDENT DEDENT mat = [ [ 1 , 1 , 1 , 0 , 1 ] , [ 1 , 0 , 2 , 0 , 1 ] , [ 0 , 0 , 1 , 0 , 1 ] , [ 1 , 0 , 1 , 1 , 0 ] ] NEW_LINE print ( minimumSteps ( mat , r , col ) ) NEW_LINE