text: Number of ways of cutting a Matrix such that atleast one cell is filled in each part | CPP implementation to find the number of ways to cut the matrix into the K parts such that each part have atleast one filled cell ; 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
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; int ways ( vector < vector < int > > & arr , int K ) { int R = arr . size ( ) ; int C = arr [ 0 ] . size ( ) ; int preSum [ R ] [ C ] ; for ( int r = R - 1 ; r >= 0 ; r -- ) { for ( int 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 ] ; } } int dp [ K + 1 ] [ R ] [ C ] ; for ( int k = 1 ; k <= K ; k ++ ) { for ( int r = R - 1 ; r >= 0 ; r -- ) { for ( int c = C - 1 ; c >= 0 ; c -- ) { if ( k == 1 ) { dp [ k ] [ r ] = ( preSum [ r ] > 0 ) ? 1 : 0 ; } else { dp [ k ] [ r ] = 0 ; for ( int r1 = r + 1 ; r1 < R ; r1 ++ ) { if ( preSum [ r ] - preSum [ r1 ] > 0 ) dp [ k ] [ r ] += dp [ k - 1 ] [ r1 ] ; } for ( int 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 ] ; } int main ( ) { vector < vector < int > > arr = { { 1 , 0 , 0 } , { 1 , 1 , 1 } , { 0 , 0 , 0 } } ; int k = 3 ; cout << ways ( arr , k ) << endl ; return 0 ; }