Queries on number of Binary sub | C # 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 Code
using System ; class GFG { static int MAX = 100 ; static int N = 5 ; static int M = 4 ; static int min ( int a , int b , int c ) { return Math . Min ( a , Math . Min ( b , c ) ) ; } static void solveQuery ( int n , int m , int [ , ] mat , int q , int [ ] a , int [ ] binary ) { int [ , ] dp = new int [ n , m ] ; int 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 = new int [ MAX ] ; int [ ] freq1 = new int [ MAX ] ; 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 ) Console . WriteLine ( freq0 [ a [ i ] ] ) ; else Console . WriteLine ( freq1 [ a [ i ] ] ) ; } } public static void Main ( ) { int n = 5 , m = 4 ; int [ , ] mat = { { 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 ) ; } }