Minimum number of 1 s present in a submatrix of given dimensions in a Binary Matrix | C ++ program for the above approach ; Function to count number of 1 s present in a sub matrix from ( start_i , start_j ) to ( end_i , end_j ) ; Stores the number of 1 s present in current submatrix ; Traverse the submatrix ; If mat [ x ] [ y ] is equal to 1 ; Increase count by 1 ; Return the total count of 1 s ; Function to find the minimum number of 1 s present in a sub - matrix of size A * B or B * A ; Stores the minimum count of 1 s ; Iterate i from 0 to N ; Iterate j from 0 to M ; If a valid sub matrix of size A * B from ( i , j ) is possible ; Count the number of 1 s present in the sub matrix of size A * B from ( i , j ) ; Update minimum if count is less than the current minimum ; If a valid sub matrix of size B * A from ( i , j ) is possible ; Count the number of 1 s in the sub matrix of size B * A from ( i , j ) ; Update minimum if count is less than the current minimum ; Return minimum as the final result ; Driver Code ; Given Input ; Function call to find the minimum number of 1 s in a submatrix of size A * B or B * A
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define P  51 NEW_LINE int count1s ( int start_i , int start_j , int end_i , int end_j , int mat [ ] [ P ] ) { int count = 0 ; for ( int x = start_i ; x < end_i ; x ++ ) { for ( int y = start_j ; y < end_j ; y ++ ) { if ( mat [ x ] [ y ] == 1 ) count ++ ; } } return count ; } int findMinimumCount ( int N , int M , int A , int B , int mat [ ] [ P ] ) { int minimum = 1e9 ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < M ; j ++ ) { if ( i + A <= N && j + B <= M ) { int count = count1s ( i , j , i + A , j + B , mat ) ; minimum = min ( count , minimum ) ; } if ( i + B <= N && j + A <= M ) { int count = count1s ( i , j , i + B , j + A , mat ) ; minimum = min ( count , minimum ) ; } } } return minimum ; } int main ( ) { int A = 2 , B = 2 ; int N = 3 , M = 4 ; int mat [ P ] [ P ] = { { 1 , 0 , 1 , 0 } , { 0 , 1 , 0 , 1 } , { 1 , 0 , 1 , 0 } } ; cout << findMinimumCount ( N , M , A , B , mat ) ; }