Number of ways of cutting a Matrix such that atleast one cell is filled in each part | Function to find the number of ways to cut the matrix into the K parts such that each part have atleast one filled cell ; Loop to find prefix sum of the given matrix ; dp ( r , c , 1 ) = 1 if preSum [ r ] else 0 ; Loop to iterate over the dp table of the given matrix ; Check if can cut horizontally at r1 , at least one apple in matrix ( r , c ) -> r1 , C - 1 ; Check if we can cut vertically at c1 , at least one apple in matrix ( r , c ) -> R - 1 , c1 ; Driver code ; Function Call
function ways ( arr , K ) { let R = arr . length ; let C = arr [ 0 ] . length ; let preSum = new Array ( R ) ; for ( let i = 0 ; i < R ; i ++ ) { preSum [ i ] = new Array ( C ) ; for ( let j = 0 ; j < C ; j ++ ) { preSum [ i ] [ j ] = 0 ; } } for ( let r = R - 1 ; r >= 0 ; r -- ) { for ( let c = C - 1 ; c >= 0 ; c -- ) { preSum [ r ] = arr [ r ] ; if ( r + 1 < R ) preSum [ r ] += preSum [ r + 1 ] ; if ( c + 1 < C ) preSum [ r ] += preSum [ r ] ; if ( r + 1 < R && c + 1 < C ) preSum [ r ] -= preSum [ r + 1 ] ; } } let dp = new Array ( K + 1 ) ; for ( let i = 0 ; i < dp . length ; i ++ ) { dp [ i ] = new Array ( R ) ; for ( let j = 0 ; j < R ; j ++ ) { dp [ i ] [ j ] = new Array ( C ) ; for ( let k = 0 ; k < C ; k ++ ) { dp [ i ] [ j ] [ k ] = 0 ; } } } for ( let k = 1 ; k <= K ; k ++ ) { for ( let r = R - 1 ; r >= 0 ; r -- ) { for ( let c = C - 1 ; c >= 0 ; c -- ) { if ( k == 1 ) { dp [ k ] [ r ] = ( preSum [ r ] > 0 ) ? 1 : 0 ; } else { dp [ k ] [ r ] = 0 ; for ( let r1 = r + 1 ; r1 < R ; r1 ++ ) { if ( preSum [ r ] - preSum [ r1 ] > 0 ) dp [ k ] [ r ] += dp [ k - 1 ] [ r1 ] ; } for ( let c1 = c + 1 ; c1 < C ; c1 ++ ) { if ( preSum [ r ] - preSum [ r ] [ c1 ] > 0 ) dp [ k ] [ r ] += dp [ k - 1 ] [ r ] [ c1 ] ; } } } } } return dp [ K ] [ 0 ] [ 0 ] ; } let arr = [ [ 1 , 0 , 0 ] , [ 1 , 1 , 1 ] , [ 0 , 0 , 0 ] ] ; let k = 3 ; document . write ( ways ( arr , k ) ) ;