Queries on number of Binary sub | CPP Program to answer queries on number of submatrix of given size ; Return the minimum of three numbers ; Solve each query on matrix ; For each of the cell . ; finding submatrix size of oth row and column . ; intermediate cells . ; Find frequency of each distinct size for 0 s and 1 s . ; Find the Cumulative Sum . ; Output the answer for each query ; Driver Program
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  100 NEW_LINE #define N  5 NEW_LINE #define M  4 NEW_LINE int min ( int a , int b , int c ) { return min ( a , min ( b , c ) ) ; } void solveQuery ( int n , int m , int mat [ N ] [ M ] , int q , int a [ ] , int binary [ ] ) { 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 ( ( mat [ i ] [ j ] == mat [ i - 1 ] [ j ] ) && ( mat [ i ] [ j ] == mat [ i ] [ j - 1 ] ) && ( mat [ i ] [ j ] == mat [ 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 freq0 [ MAX ] = { 0 } , freq1 [ MAX ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { if ( mat [ i ] [ j ] == 0 ) freq0 [ dp [ i ] [ j ] ] ++ ; else freq1 [ dp [ i ] [ j ] ] ++ ; } } for ( int i = max - 1 ; i >= 0 ; i -- ) { freq0 [ i ] += freq0 [ i + 1 ] ; freq1 [ i ] += freq1 [ i + 1 ] ; } for ( int i = 0 ; i < q ; i ++ ) { if ( binary [ i ] == 0 ) cout << freq0 [ a [ i ] ] << endl ; else cout << freq1 [ a [ i ] ] << endl ; } } int main ( ) { int n = 5 , m = 4 ; int mat [ N ] [ M ] = { { 0 , 0 , 1 , 1 } , { 0 , 0 , 1 , 0 } , { 0 , 1 , 1 , 1 } , { 1 , 1 , 1 , 1 } , { 0 , 1 , 1 , 1 } } ; int q = 2 ; int a [ ] = { 2 , 2 } ; int binary [ ] = { 1 , 0 } ; solveQuery ( n , m , mat , q , a , binary ) ; return 0 ; }