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 code
using System ; class GFG { static int minCells ( int [ , ] mat , int m , int n ) { int [ , ] dp = new int [ m , n ] ; for ( int i = 0 ; i < m ; i ++ ) for ( int j = 0 ; j < n ; j ++ ) dp [ i , j ] = int . MaxValue ; dp [ 0 , 0 ] = 1 ; for ( int i = 0 ; i < m ; i ++ ) { for ( int j = 0 ; j < n ; j ++ ) { if ( dp [ i , j ] != int . MaxValue && ( 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 . MaxValue && ( 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 . MaxValue ) return dp [ m - 1 , n - 1 ] ; return - 1 ; } public static void Main ( ) { int [ , ] mat = { { 2 , 3 , 2 , 1 , 4 } , { 3 , 2 , 5 , 8 , 2 } , { 1 , 1 , 2 , 2 , 1 } } ; int m = 3 , n = 5 ; Console . WriteLine ( " Minimum ▁ number ▁ of ▁ " + " cells ▁ = ▁ " + minCells ( mat , m , n ) ) ; } }