Given a binary matrix V[][] of dimensions N * M, wherein each cell is either empty or blocked marked by a 0 and 1 respectively, the task is to count the number of ways to select K consecutive empty cells from the same row or column.
Examples:
Input: V[][] = {{1, 1, 0}, {0, 0, 0}}, K = 2
Output: 3
Explanation:
Considering 1-based indexing, 2 consecutive empty cells can be selected in the following ways:
[(1, 3), (2, 3)], [(2, 1), (2, 2)], [(2, 2), (2, 3)]
Input: V[][] = {{1, 1, 0}, {0, 0, 0}, {0, 0, 0}}, K = 1
Output: 9
Explanation:
It is possible to select all the cells since every cell is empty.
Approach:
The idea is to traverse the matrix row-wise and for each row, count the total number of empty consecutive cells.
Follow the steps below to solve the problem:
- Traverse the matrix row-wise and count the number of consecutive cells. If the count becomes equal to or exceeds K, increase the count by 1.
- Every time a blocked cell is encountered, reset the count of consecutive empty cells to 0.
- Repeat the above steps while traversing the matrix column-wise as well if K ? 1.
- Return the final count of cells obtained.
Below is the implementation of the above approach:
C++
// C++ program to find no of ways// to select K consecutive empty// cells from a row or column#include <bits/stdc++.h>using namespace std;// Function to Traverse// the matrix row wiseint rowWise(char* v, int n, int m, int k){ // Initialize ans int ans = 0; // Traverse row wise for (int i = 0; i < n; i++) { // Initialize no of // consecutive empty // cells int countcons = 0; for (int j = 0; j < m; j++) { // Check if blocked cell is // encountered then reset // countcons to 0 if (*(v + i * m + j) == '1') { countcons = 0; } // Check if empty cell is // encountered, then // increment countcons else { countcons++; } // Check if number of empty // consecutive cells // is greater or equal // to K, increment the ans if (countcons >= k) { ans++; } } } // Return the count return ans;}// Function to Traverse the// matrix column wiseint colWise(char* v, int n, int m, int k){ // Initialize ans int ans = 0; // Traverse column wise for (int i = 0; i < m; i++) { // Initialize no of // consecutive empty cells int countcons = 0; for (int j = 0; j < n; j++) { // Check if blocked cell is // encountered then reset // countcons to 0 if (*(v + j * n + i) == '1') { countcons = 0; } // Check if empty cell is // encountered, increment // countcons else { countcons++; } // Check if number of empty // consecutive cells // is greater than or equal // to K, increment the ans if (countcons >= k) { ans++; } } } // Return the count return ans;}// Driver Codeint main(){ int n = 3, m = 3, k = 1; char v[n][m] = { '0', '0', '0', '0', '0', '0', '0', '0', '0' }; // If k = 1 only traverse row wise if (k == 1) { cout << rowWise(v[0], n, m, k); } // Traverse both row and column wise else { cout << colWise(v[0], n, m, k) + rowWise(v[0], n, m, k); } return 0;} |
Java
// Java program to find no of ways// to select K consecutive empty// cells from a row or columnimport java.util.*;class GFG{// Function to Traverse// the matrix row wisestatic int rowWise(char [][]v, int n, int m, int k){ // Initialize ans int ans = 0; // Traverse row wise for(int i = 0; i < n; i++) { // Initialize no of // consecutive empty // cells int countcons = 0; for(int j = 0; j < m; j++) { // Check if blocked cell is // encountered then reset // countcons to 0 if (v[i][j] == '1') { countcons = 0; } // Check if empty cell is // encountered, then // increment countcons else { countcons++; } // Check if number of empty // consecutive cells // is greater or equal // to K, increment the ans if (countcons >= k) { ans++; } } } // Return the count return ans;}// Function to Traverse the// matrix column wisestatic int colWise(char [][]v, int n, int m, int k){ // Initialize ans int ans = 0; // Traverse column wise for(int i = 0; i < m; i++) { // Initialize no of // consecutive empty cells int countcons = 0; for(int j = 0; j < n; j++) { // Check if blocked cell is // encountered then reset // countcons to 0 if (v[j][i] == '1') { countcons = 0; } // Check if empty cell is // encountered, increment // countcons else { countcons++; } // Check if number of empty // consecutive cells // is greater than or equal // to K, increment the ans if (countcons >= k) { ans++; } } } // Return the count return ans;}// Driver Codepublic static void main(String[] args){ int n = 3, m = 3, k = 1; char v[][] = { { '0', '0', '0' }, { '0', '0', '0' }, { '0', '0', '0' } }; // If k = 1 only traverse row wise if (k == 1) { System.out.print(rowWise(v, n, m, k)); } // Traverse both row and column wise else { System.out.print(colWise(v, n, m, k) + rowWise(v, n, m, k)); }}}// This code is contributed by amal kumar choubey |
Python3
# Python 3 program to find no of ways# to select K consecutive empty# cells from a row or column# Function to Traverse# the matrix row wisedef rowWise(v, n, m, k): # Initialize ans ans = 0 # Traverse row wise for i in range (n): # Initialize no of # consecutive empty # cells countcons = 0 for j in range (m): # Check if blocked cell is # encountered then reset # countcons to 0 if (v[i][j] == '1'): countcons = 0 # Check if empty cell is # encountered, then # increment countcons else: countcons += 1 # Check if number of empty # consecutive cells # is greater or equal # to K, increment the ans if (countcons >= k): ans += 1 # Return the count return ans# Function to Traverse the# matrix column wisedef colWise(v, n, m, k): # Initialize ans ans = 0 # Traverse column wise for i in range (m): # Initialize no of # consecutive empty cells countcons = 0 for j in range (n): # Check if blocked cell is # encountered then reset # countcons to 0 if (v[j][i] == '1'): countcons = 0 # Check if empty cell is # encountered, increment # countcons else: countcons += 1 # Check if number of empty # consecutive cells # is greater than or equal # to K, increment the ans if (countcons >= k): ans += 1 # Return the count return ans# Driver Codeif __name__ == "__main__": n = 3 m = 3 k = 1 v = [['0', '0', '0'], ['0', '0', '0'], ['0', '0', '0']] # If k = 1 only # traverse row wise if (k == 1): print (rowWise(v, n, m, k)) # Traverse both row # and column wise else: print (colWise(v, n, m, k) + rowWise(v, n, m, k)) # This code is contributed by Chitranayal |
C#
// C# program to find no of ways // to select K consecutive empty // cells from a row or column using System;class GFG{ // Function to Traverse // the matrix row wise static int rowWise(char [,]v, int n, int m, int k) { // Initialize ans int ans = 0; // Traverse row wise for(int i = 0; i < n; i++) { // Initialize no of // consecutive empty // cells int countcons = 0; for(int j = 0; j < m; j++) { // Check if blocked cell is // encountered then reset // countcons to 0 if (v[i, j] == '1') { countcons = 0; } // Check if empty cell is // encountered, then // increment countcons else { countcons++; } // Check if number of empty // consecutive cells // is greater or equal // to K, increment the ans if (countcons >= k) { ans++; } } } // Return the count return ans; } // Function to Traverse the // matrix column wise static int colWise(char [,]v, int n, int m, int k) { // Initialize ans int ans = 0; // Traverse column wise for(int i = 0; i < m; i++) { // Initialize no of // consecutive empty cells int countcons = 0; for(int j = 0; j < n; j++) { // Check if blocked cell is // encountered then reset // countcons to 0 if (v[j, i] == '1') { countcons = 0; } // Check if empty cell is // encountered, increment // countcons else { countcons++; } // Check if number of empty // consecutive cells // is greater than or equal // to K, increment the ans if (countcons >= k) { ans++; } } } // Return the count return ans; } // Driver Code public static void Main(String[] args) { int n = 3, m = 3, k = 1; char [,]v = { { '0', '0', '0' }, { '0', '0', '0' }, { '0', '0', '0' } }; // If k = 1 only traverse row wise if (k == 1) { Console.Write(rowWise(v, n, m, k)); } // Traverse both row and column wise else { Console.Write(colWise(v, n, m, k) + rowWise(v, n, m, k)); } } } // This code is contributed by amal kumar choubey |
Javascript
<script>// Javascript program to find no of ways// to select K consecutive empty// cells from a row or column// Function to Traverse// the matrix row wisefunction rowWise(v, n, m, k){ // Initialize ans var ans = 0; // Traverse row wise for (var i = 0; i < n; i++) { // Initialize no of // consecutive empty // cells var countcons = 0; for (var j = 0; j < m; j++) { // Check if blocked cell is // encountered then reset // countcons to 0 if ((v + i * m + j) == '1') { countcons = 0; } // Check if empty cell is // encountered, then // increment countcons else { countcons++; } // Check if number of empty // consecutive cells // is greater or equal // to K, increment the ans if (countcons >= k) { ans++; } } } // Return the count return ans;}// Function to Traverse the// matrix column wisefunction colWise(v, n, m, k){ // Initialize ans var ans = 0; // Traverse column wise for (var i = 0; i < m; i++) { // Initialize no of // consecutive empty cells var countcons = 0; for (var j = 0; j < n; j++) { // Check if blocked cell is // encountered then reset // countcons to 0 if ((v + j * n + i) == '1') { countcons = 0; } // Check if empty cell is // encountered, increment // countcons else { countcons++; } // Check if number of empty // consecutive cells // is greater than or equal // to K, increment the ans if (countcons >= k) { ans++; } } } // Return the count return ans;}// Driver Codevar n = 3, m = 3, k = 1;var v = ['0', '0', '0', '0', '0', '0', '0', '0', '0']; // If k = 1 only traverse row wiseif (k == 1) { document.write( rowWise(v[0], n, m, k)); }// Traverse both row and column wiseelse { document.write( colWise(v[0], n, m, k) + rowWise(v[0], n, m, k));}// This code is contributed by itsok.</script> |
Output:
9
Time Complexity: O(N * M)
Space Complexity: O(N * M)
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!
