Given an integer K and a matrix mat[][] containing 1 and 0, where 1 denotes the cell is filled and 0 denotes an empty cell. The task is to find the number of ways to cut the matrix into K parts using K-1 cuts such that each part of the matrix contains atleast one filled cell.
For each cut, there must be a direction either horizontal or vertical. Then you choose a cut position at the cell boundary and cut the matrix into two parts. If you cut the matrix vertically, the left part of the matrix will not be used again for further process. If you cut the matrix horizontally, the upper part of the matrix will not be used again.
Examples:
Input: mat[][] = {{1, 0, 0}, {1, 1, 1}, {0, 0, 0}}, K = 3
Output: 3
Explanation:
Input: matrix = {{1, 0, 0}, {1, 1, 0}, {0, 0, 0}}, K = 3
Output: 1
Approach: The idea is to use Dynamic Programming to compute the number of ways of cutting a matrix with atleast one filled cell.
- Compute the prefix sum of the matrix such that we can compute a particular portion of the matrix contains a filled cell or not in O(1) time.
- Define a dp table to store the number of ways to cut the pizza in K parts, where dp[k][r] denotes the number of ways to cut the matrix into K parts from top left to Rth row and Cth Column.
- Finally, iterate over for every possible matrix and check that if the matrix can be cut into the two parts upto that index and both part is valid or not.
Below is the implementation of the above approach:
C++
// 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#include <bits/stdc++.h>using namespace std;// Function to find the number of// ways to cut the matrix into the// K parts such that each part have// atleast one filled cellint ways(vector<vector<int>> &arr, int K){ int R = arr.size(); int C = arr[0].size(); int preSum[R][C]; // Loop to find prefix sum of the // given matrix 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]; } } // dp(r, c, 1) = 1 // if preSum[r] else 0 int dp[K + 1][R][C]; // Loop to iterate over the dp // table of the given matrix 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++) { // Check if can cut horizontally // at r1, at least one apple in // matrix (r, c) -> r1, C-1 if (preSum[r] - preSum[r1] > 0) dp[k][r] += dp[k - 1][r1]; } for (int c1 = c + 1; c1 < C; c1++) { // Check if we can cut vertically // at c1, at least one apple in // matrix (r, c) -> R-1, c1 if (preSum[r] - preSum[r][c1] > 0) dp[k][r] += dp[k - 1][r][c1]; } } } } } return dp[K][0][0];}// Driver codeint main(){ vector<vector<int>> arr = {{1, 0, 0}, {1, 1, 1}, {0, 0, 0}}; int k = 3; // Function Call cout << ways(arr, k) << endl; return 0;}// This code is contributed by sanjeev2552 |
Java
// Java implementation to find the // number of ways to cut the matrix // into the K parts such that each // part have atleast one filled cell import java.util.*;import java.lang.*;import java.io.*;class GFG{// Function to find the number of// ways to cut the matrix into the// K parts such that each part have// atleast one filled cell static int ways(int[][] arr, int K){ int R = arr.length; int C = arr[0].length; int[][] preSum = new int[R][C]; // Loop to find prefix sum of the // given matrix 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]; } } // dp(r, c, 1) = 1 // if preSum[r] else 0 int[][][] dp = new int[K + 1][R][C]; // Loop to iterate over the dp // table of the given matrix 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++) { // Check if can cut horizontally // at r1, at least one apple in // matrix (r, c) -> r1, C-1 if (preSum[r] - preSum[r1] > 0) dp[k][r] += dp[k - 1][r1]; } for(int c1 = c + 1; c1 < C; c1++) { // Check if we can cut vertically // at c1, at least one apple in // matrix (r, c) -> R-1, c1 if (preSum[r] - preSum[r][c1] > 0) dp[k][r] += dp[k - 1][r][c1]; } } } } } return dp[K][0][0]; }// Driver codepublic static void main(String[] args){ int[][] arr = { { 1, 0, 0 }, { 1, 1, 1 }, { 0, 0, 0 } }; int k = 3; // Function Call System.out.println(ways(arr, k)); }}// This code is contributed by offbeat |
Python3
# Python3 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 celldef ways(arr, k): R = len(arr) C = len(arr[0]) K = k preSum = [[0 for _ in range(C)]\ for _ in range(R)] # Loop to find prefix sum of the # given matrix for r in range(R-1, -1, -1): for c in range(C-1, -1, -1): 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 and c + 1 < C: preSum[r] -= preSum[r + 1] # dp(r, c, 1) = 1 # if preSum[r] else 0 dp = [[[0 for _ in range(C)]\ for _ in range(R)]\ for _ in range(K + 1)] # Loop to iterate over the dp # table of the given matrix for k in range(1, K + 1): for r in range(R-1, -1, -1): for c in range(C-1, -1, -1): if k == 1: dp[k][r] = 1 \ if preSum[r] > 0\ else 0 else: dp[k][r] = 0 for r1 in range(r + 1, R): # Check if can cut horizontally # at r1, at least one apple in # matrix (r, c) -> r1, C-1 if preSum[r] - preSum[r1] > 0: dp[k][r] += dp[k-1][r1] for c1 in range(c + 1, C): # Check if we can cut vertically # at c1, at least one apple in # matrix (r, c) -> R-1, c1 if preSum[r] - preSum[r][c1] > 0: dp[k][r] += dp[k-1][r][c1] return dp[K][0][0] # Driver Codeif __name__ == "__main__": arr = [[1, 0, 0], [1, 1, 1], [0, 0, 0]] k = 3 # Function Call print(ways(arr, k)) |
C#
// C# implementation to find the// number of ways to cut the matrix// into the K parts such that each// part have atleast one filled cellusing System;class GFG { // Function to find the number of // ways to cut the matrix into the // K parts such that each part have // atleast one filled cell static int ways(int[, ] arr, int K) { int R = arr.GetLength(0); int C = arr.GetLength(1); int[, ] preSum = new int[R, C]; // Loop to find prefix sum of the // given matrix for (int r = R - 1; r >= 0; r--) { for (int c = C - 1; c >= 0; c--) { preSum[r, c] = arr[r, c]; if (r + 1 < R) preSum[r, c] += preSum[r + 1, c]; if (c + 1 < C) preSum[r, c] += preSum[r, c + 1]; if (r + 1 < R && c + 1 < C) preSum[r, c] -= preSum[r + 1, c + 1]; } } // dp(r, c, 1) = 1 // if preSum[r] else 0 int[, , ] dp = new int[K + 1, R, C]; // Loop to iterate over the dp // table of the given matrix 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, c] = (preSum[r, c] > 0) ? 1 : 0; } else { dp[k, r, c] = 0; for (int r1 = r + 1; r1 < R; r1++) { // Check if can cut horizontally // at r1, at least one apple in // matrix (r, c) -> r1, C-1 if (preSum[r, c] - preSum[r1, c] > 0) dp[k, r, c] += dp[k - 1, r1, c]; } for (int c1 = c + 1; c1 < C; c1++) { // Check if we can cut // vertically at c1, at least // one apple in matrix (r, c) -> // R-1, c1 if (preSum[r, c] - preSum[r, c1] > 0) dp[k, r, c] += dp[k - 1, r, c1]; } } } } } return dp[K, 0, 0]; } // Driver code public static void Main(string[] args) { int[, ] arr = { { 1, 0, 0 }, { 1, 1, 1 }, { 0, 0, 0 } }; int k = 3; // Function Call Console.WriteLine(ways(arr, k)); }}// This code is contributed by ukasp. |
Javascript
<script>// Javascript 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 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; } } // Loop to find prefix sum of the // given matrix 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]; } } // dp(r, c, 1) = 1 // if preSum[r] else 0 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; } } } // Loop to iterate over the dp // table of the given matrix 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++) { // Check if can cut horizontally // at r1, at least one apple in // matrix (r, c) -> r1, C-1 if (preSum[r] - preSum[r1] > 0) dp[k][r] += dp[k - 1][r1]; } for(let c1 = c + 1; c1 < C; c1++) { // Check if we can cut vertically // at c1, at least one apple in // matrix (r, c) -> R-1, c1 if (preSum[r] - preSum[r][c1] > 0) dp[k][r] += dp[k - 1][r][c1]; } } } } } return dp[K][0][0];}// Driver codelet arr = [[1, 0, 0 ], [ 1, 1, 1 ], [ 0, 0, 0 ]]; let k = 3; // Function Call document.write(ways(arr, k));// This code is contributed by avanitrachhadiya2155.</script> |
Output:
3
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
