Minimum cells required to reach destination with jumps equal to cell values | C ++ 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 ; initially no cells can be reached ; base case ; building up the dp [ ] [ ] matrix ; dp [ i ] [ j ] != INT_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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define SIZE  100 NEW_LINE int minCells ( int mat [ SIZE ] [ SIZE ] , int m , int n ) { int dp [ m ] [ n ] ; for ( int i = 0 ; i < m ; i ++ ) for ( int j = 0 ; j < n ; j ++ ) dp [ i ] [ j ] = INT_MAX ; dp [ 0 ] [ 0 ] = 1 ; for ( int i = 0 ; i < m ; i ++ ) { for ( int j = 0 ; j < n ; j ++ ) { if ( dp [ i ] [ j ] != INT_MAX && ( j + mat [ i ] [ j ] ) < n && ( dp [ i ] [ j ] + 1 ) < dp [ i ] [ j + mat [ i ] [ j ] ] ) dp [ i ] [ j + mat [ i ] [ j ] ] = dp [ i ] [ j ] + 1 ; if ( dp [ i ] [ j ] != INT_MAX && ( i + mat [ i ] [ j ] ) < m && ( dp [ i ] [ j ] + 1 ) < dp [ i + mat [ i ] [ j ] ] [ j ] ) dp [ i + mat [ i ] [ j ] ] [ j ] = dp [ i ] [ j ] + 1 ; } } if ( dp [ m - 1 ] [ n - 1 ] != INT_MAX ) return dp [ m - 1 ] [ n - 1 ] ; return -1 ; } int main ( ) { int mat [ SIZE ] [ SIZE ] = { { 2 , 3 , 2 , 1 , 4 } , { 3 , 2 , 5 , 8 , 2 } , { 1 , 1 , 2 , 2 , 1 } } ; int m = 3 , n = 5 ; cout << " Minimum ▁ number ▁ of ▁ cells ▁ = ▁ " << minCells ( mat , m , n ) ; return 0 ; }