Find minimum steps required to reach the end of a matrix | Set 2 | Python3 implementation of the approach ; 2d array to store states of dp ; Array to determine whether a state has been solved before ; Function to return the minimum steps required ; Base cases ; If a state has been solved before it won 't be evaluated again ; Recurrence relation ; Driver code
import numpy as np NEW_LINE n = 3 NEW_LINE dp = np . zeros ( ( n , n ) ) NEW_LINE v = np . zeros ( ( n , n ) ) ; NEW_LINE def minSteps ( i , j , arr ) : NEW_LINE INDENT if ( i == n - 1 and j == n - 1 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( i > n - 1 or j > n - 1 ) : NEW_LINE INDENT return 9999999 ; NEW_LINE DEDENT if ( v [ i ] [ j ] ) : NEW_LINE INDENT return dp [ i ] [ j ] ; NEW_LINE DEDENT v [ i ] [ j ] = 1 ; NEW_LINE dp [ i ] [ j ] = 9999999 ; NEW_LINE for k in range ( max ( 0 , arr [ i ] [ j ] + j - n + 1 ) , min ( n - i - 1 , arr [ i ] [ j ] ) + 1 ) : NEW_LINE INDENT dp [ i ] [ j ] = min ( dp [ i ] [ j ] , minSteps ( i + k , j + arr [ i ] [ j ] - k , arr ) ) ; NEW_LINE DEDENT dp [ i ] [ j ] += 1 ; NEW_LINE return dp [ i ] [ j ] ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ [ 4 , 1 , 2 ] , [ 1 , 1 , 1 ] , [ 2 , 1 , 1 ] ] ; NEW_LINE ans = minSteps ( 0 , 0 , arr ) ; NEW_LINE if ( ans >= 9999999 ) : NEW_LINE INDENT print ( - 1 ) ; NEW_LINE DEDENT else : NEW_LINE INDENT print ( ans ) ; NEW_LINE DEDENT DEDENT