Minimum cells required to reach destination with jumps equal to cell values | Python3 implementation to count minimum cells required to be covered to reach destination ; function to count minimum cells required to be covered to reach destination ; to store min cells required to be covered to reach a particular cell ; base case ; building up the dp [ ] [ ] matrix ; dp [ i ] [ j ] != MAX denotes that cell ( i , j ) can be reached from cell ( 0 , 0 ) and the other half of the condition finds the cell on the right that can be reached from ( i , j ) ; the other half of the condition finds the cell right below that can be reached from ( i , j ) ; it true then cell ( m - 1 , n - 1 ) can be reached from cell ( 0 , 0 ) and returns the minimum number of cells covered ; cell ( m - 1 , n - 1 ) cannot be reached from cell ( 0 , 0 ) ; Driver program to test above
SIZE = 100 NEW_LINE MAX = 10000000 NEW_LINE def minCells ( mat , m , n ) : NEW_LINE INDENT dp = [ [ MAX for i in range ( n ) ] for i in range ( m ) ] NEW_LINE dp [ 0 ] [ 0 ] = 1 NEW_LINE for i in range ( m ) : NEW_LINE INDENT for j in range ( n ) : NEW_LINE INDENT if ( dp [ i ] [ j ] != MAX and ( j + mat [ i ] [ j ] ) < n and ( dp [ i ] [ j ] + 1 ) < dp [ i ] [ j + mat [ i ] [ j ] ] ) : NEW_LINE INDENT dp [ i ] [ j + mat [ i ] [ j ] ] = dp [ i ] [ j ] + 1 NEW_LINE DEDENT if ( dp [ i ] [ j ] != MAX and ( i + mat [ i ] [ j ] ) < m and ( dp [ i ] [ j ] + 1 ) < dp [ i + mat [ i ] [ j ] ] [ j ] ) : NEW_LINE INDENT dp [ i + mat [ i ] [ j ] ] [ j ] = dp [ i ] [ j ] + 1 NEW_LINE DEDENT DEDENT DEDENT if ( dp [ m - 1 ] [ n - 1 ] != MAX ) : NEW_LINE INDENT return dp [ m - 1 ] [ n - 1 ] NEW_LINE DEDENT return - 1 NEW_LINE DEDENT mat = [ [ 2 , 3 , 2 , 1 , 4 ] , [ 3 , 2 , 5 , 8 , 2 ] , [ 1 , 1 , 2 , 2 , 1 ] ] NEW_LINE m = 3 NEW_LINE n = 5 NEW_LINE print ( " Minimum ▁ number ▁ of ▁ cells ▁ = ▁ " , minCells ( mat , m , n ) ) NEW_LINE