#codingexercise

We were discussing counting submatrices of same binary value of size k x k in an overall rectangular matrix.  

Another way to do it is to use dynamic programming as discussed here. 

void GetCountSquareBooleanSubMatrices(int [,] A, int rows, int cols, int binary, int size) 

{ 

Var dp = new int[rows, cols]; 

Int max = 1; 

for (int I = 0; I < rows; i++) 

for (int j = 0; j < cols; j++) 

{ 

If ((i-1 >= 0 && A[I,j] == A[i-1,j) && 

                   (j-1>= 0 && A[I,j] == A[I,j – 1]) && 

                   (i-1 >= 0 && j-1 >= 0 && A[I, j] == A[i-1, j-1]))  

               { 

dp[i, j] =  Math.Min(dp[I, j-1], dp[i-1,j], dp[i-1,j-1]) + 1; 

                             if (dp[i, j] > max) { 

max = dp[i, j]; 

                             } 

               } else { 

                              dp[I, j] = 1; 

               } 

} 

} 

int countZeros[max+1]; 

int countOnes[max+1]; 

for (int I =0; I < rows; i++) 

    for (int j = 0; j < cols; j++) 

           { 

                      If (A[i, j] == 0){ 

                           countZeros[dp[i,j]]++; 

                      } else { 

                           countOnes[dp[i,j]]++; 

                      } 

           } 

For (int k = max-1; k>= 0; k--) 

{ 

countZeros[i] += countZeros[i+1]; 

               countOnes[i] += countOnes[i+1]; 

} 

If (size > max) { 

      return 0; 

} 

If (binary == 0) { 

       return countZeros[size]; 

} else { 

       return countOnes[size]; 

} 

}