Queries to count minimum flips required to fill a binary submatrix with 0 s only | C # program for the above approach ; Function to compute the matrix prefixCnt [ M ] [ N ] from mat [ M ] [ N ] such that prefixCnt [ i ] [ j ] stores the count of 0 's from (0, 0) to (i, j) ; Initialize prefixCnt [ i ] [ j ] with 1 if mat [ i , j ] is 0 ; Otherwise , assign with 0 ; Calculate prefix sum for each row ; Calculate prefix sum for each column ; Function to compute count of 0 's in submatrix from (pi, pj) to (qi, qj) from prefixCnt[M][N] ; Initialize that count of 0 's  in the sub-matrix within  indices (0, 0) to (qi, qj) ; Subtract count of 0 's within  indices (0, 0) and (pi-1, qj) ; Subtract count of 0 's within  indices (0, 0) and (qi, pj-1) ; Add prefixCnt [ pi - 1 ] [ pj - 1 ] because its value has been added ; once but subtracted twice ; Function to count the 0 s in the each given submatrix ; Stores the prefix sum of each row and column ; Compute matrix prefixCnt [ , ] ; Function Call for each query ; Driver Code ; Given matrix ; Function Call
using System ; class GFG { static int M = 6 ; static int N = 7 ; static void preCompute ( int [ , ] mat , int [ , ] prefixCnt ) { for ( int i = 0 ; i < M ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) { if ( mat [ i , j ] == 0 ) { prefixCnt [ i , j ] = 1 ; } else { prefixCnt [ i , j ] = 0 ; } } } for ( int i = 0 ; i < M ; i ++ ) for ( int j = 1 ; j < N ; j ++ ) prefixCnt [ i , j ] += prefixCnt [ i , j - 1 ] ; for ( int i = 1 ; i < M ; i ++ ) for ( int j = 0 ; j < N ; j ++ ) prefixCnt [ i , j ] += prefixCnt [ i - 1 , j ] ; } static int countQuery ( int [ , ] prefixCnt , int pi , int pj , int qi , int qj ) { int cnt = prefixCnt [ qi , qj ] ; if ( pi > 0 ) cnt -= prefixCnt [ pi - 1 , qj ] ; if ( pj > 0 ) cnt -= prefixCnt [ qi , pj - 1 ] ; if ( pi > 0 && pj > 0 ) cnt += prefixCnt [ pi - 1 , pj - 1 ] ; return cnt ; } static void count0s ( int [ , ] mat , int [ , ] Q , int sizeQ ) { int [ , ] prefixCnt = new int [ M , N ] ; preCompute ( mat , prefixCnt ) ; for ( int i = 0 ; i < sizeQ ; i ++ ) { Console . Write ( countQuery ( prefixCnt , Q [ i , 0 ] , Q [ i , 1 ] , Q [ i , 2 ] , Q [ i , 3 ] ) + " ▁ " ) ; } } public static void Main ( string [ ] args ) { int [ , ] mat = { { 0 , 1 , 0 , 1 , 1 , 1 , 0 } , { 1 , 0 , 1 , 1 , 1 , 0 , 1 } , { 1 , 1 , 0 , 0 , 1 , 1 , 0 } , { 1 , 1 , 1 , 1 , 1 , 0 , 1 } , { 0 , 0 , 1 , 0 , 1 , 1 , 1 } , { 1 , 1 , 0 , 1 , 1 , 0 , 1 } } ; int [ , ] Q = { { 0 , 1 , 3 , 2 } , { 2 , 2 , 4 , 5 } , { 4 , 3 , 5 , 6 } } ; int sizeQ = Q . GetLength ( 0 ) ; count0s ( mat , Q , sizeQ ) ; } }