Queries on number of Binary sub-matrices of Given size in C++

In this problem, we are given a binary matrix bin[][] of size nXm. Our task is to solve all q queries. For query(x, y), we need to find the number of submatrix of size x*x such that all the elements of array y (binary number).

Problem description

Here, we need to count the total number of sub-matrix of a given size that consists of only one of the two bits i.e. sub-matrix will all elements 0/1.

Let’s take an example to understand the problem,

Input

n = 3 , m = 4 bin[][] = {{ 1, 1, 0, 1} { 1, 1, 1, 0} { 0, 1, 1, 1}} q = 1 q1 = (2, 1)

Output

2

Explanation

All sub-matrix of size 2 with all element 1 are −

{{ 1, 1, 0, 1} { 1, 1, 1, 0} { 0, 1, 1, 1}} {{ 1, 1, 0, 1} { 1, 1, 1, 0} { 0, 1, 1, 1}}

The solution to this problem is using the Dynamic programming approach. To solve, we will maintain a 2D matric DP[][] to store the largest submatrix of the same bit. i.e. DP[i][j] will store the value of sub-matrix whose end index is (i, j), and all the elements are the same.

For your understanding, if DP[4][5] = 2, elements at bin[3][4], bin[3][5], bin[4][4] and bin[4][5] are same.

So, for finding DP[i][j], we have two cases −

Case 1 − if i = 0 orj = 0 : DP[i][j] = 1, as only one sub-matrix can be possible.

Case 2 − otherwise, bin[i-(k-1)][j] = bin[i][j - (k-1)] …: in this casae DP[i][j] = min(DP[i][j-1] , DP[i -1][j], DP[i-1][j-1] ) + 1. This will contribute to the sub-matrix like, we require. Let’s generalise, the case with k = 2, i.e. if we consider a sub-matrix of size 2X2. Then we need to check if bin[i][j] = bin[i] [j - 1] = bin[i- 1][j] = bin[i -1 ][j -1 ], if it is possible then, we will find the DP[i][j] for k =2 .

If the case 2 conditions are not met, we will set DP[i][j] = 1, which can be treated as a default value.

This value of DP[i][j] can be for a set bit or unset bit. We will check the value of bin[i][j] to see which of the set or unset values the k value belongs. To find the frequencies, we will create two arrays, zeroFrequrency to store the frequency of sub-matrix that is generated for 0. And oneFrequrency to store the frequency of sub-matrix that is generated for 1.

Program to illustrate the working of our solution,

Eample

 Live Demo

#include <iostream> using namespace std; #define N 3 #define M 4 int min(int a, int b, int c) {    if (a <= b && a <= c)    return a;    else if (b <= a && b <= c)    return b;    else    return c; } int solveQuery(int n, int m, int bin[N][M], int x, int y){    int DP[n][m], max = 1;    for (int i = 0; i < n; i++) {       for (int j = 0; j < m; j++) {          if (i == 0 || j == 0)          DP[i][j] = 1;          else if ((bin[i][j] == bin[i - 1][j]) && (bin[i][j] == bin[i][j - 1]) && (bin[i][j] == bin[i - 1][j - 1])) {             DP[i][j] = min(DP[i - 1][j], DP[i - 1][j - 1], DP[i][j - 1]) + 1;             if (max < DP[i][j])             max = DP[i][j];          }          else          DP[i][j] = 1;       }    }    int zeroFrequency[n+m] = { 0 }, oneFrequency[n+m] = { 0 };    for (int i = 0; i < n; i++) {       for (int j = 0; j < m; j++) {          if (bin[i][j] == 0)          zeroFrequency[DP[i][j]]++;          else          oneFrequency[DP[i][j]]++;       }    }    for (int i = max - 1; i >= 0; i--) {       zeroFrequency[i] += zeroFrequency[i + 1];       oneFrequency[i] += oneFrequency[i + 1];    }    if (y == 0)    return zeroFrequency[x];    else    return oneFrequency[x]; } int main(){    int n = 3, m = 4;    int mat[N][M] =    {{ 1, 1, 0, 1},    { 1, 1, 1, 0},    { 0, 1, 1, 1}};    int Q = 2;    int query[Q][2] = {{ 2, 1}, { 1, 0}};    for(int i = 0; i < Q; i++){       cout<<"For Query "<<(i+1)<<": The number of Binary sub-matrices of Given size is "            <<solveQuery(n, m, mat, query[i][0], query[i][1])<<"\n";    }    return 0; }

Output

For Query 1: The number of Binary sub-matrices of Given size is 2 For Query 2: The number of Binary sub-matrices of Given size is 3