Count of ways to select K consecutive empty cells from a given Matrix

0 0 9 minutes read

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 wise
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 * 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 wise
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 * 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 Code
int 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 column
import java.util.*;
 
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) 
    {
        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 wise
def 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 wise
def 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 Code
if __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 wise
function 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 wise
function 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 Code
var n = 3, m = 3, k = 1;
var v = ['0', '0', '0',
                 '0', '0', '0',
                 '0', '0', '0'];
                  
// If k = 1 only traverse row wise
if (k == 1) {
    document.write( rowWise(v[0], n, m, k));   
}
 
// Traverse both row and column wise
else {
    document.write( colWise(v[0], n, m, k)
                + rowWise(v[0], n,
                          m, k));
}
 
// This code is contributed by itsok.
</script>

Output:

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 zambiatek!