Minimum number of 1s present in a submatrix of given dimensions in a Binary Matrix

#include <bits/stdc++.h>

using namespace std;

  

#define P 51

  

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);

}

Let's block ads! (Why?)