Program to count number of square submatix of 1s in the given matrix in C++

Suppose we have a 2d binary matrix, we have to find the total number of submatrices with all 1 s.

So, if the input is like

then the output will be 10, as there five 1 x 1 matrix, two 2 x 1 matrix. two 1 x 2 matrices. And one 2 x 2 matrix.

To solve this, we will follow these steps −

• Define a function getAns(), this will take an array a,

• ret := 0

• n := size of a

• Define an array v of size n

• Define one stack st

• for initialize i := 0, when i < size of a, update (increase i by 1), do −

  • while (st is not empty and a[top element of st] >= a[i]), do −

    • pop from st

  • if st is not empty, then −

    • prev := top element of st

    • v[i] := v[i] + v[prev]

    • v[i] := v[i] + a[i] * (i - prev)

  • Otherwise

    • v[i] := v[i] + a[i] * (i + 1)

  • insert i into st

• for each i in v −

  • ret := ret + i

• return ret

• From the main method do the following −

• ret := 0

• n := size of v

• m := (if n is non-zero, then size of v[0], otherwise 0)

• Define an array temp of size m

• for initialize i := 0, when i < n, update (increase i by 1), do −

  • for initialize j := 0, when j < m, update (increase j by 1), do −

    • temp[j] := (if v[i, j] is non-zero, then temp[j] + 1, otherwise 0)

  • ret := ret + getAns(temp)

• return ret

Example 

Let us see the following implementation to get better understanding −

 Live Demo

#include <bits/stdc++.h> using namespace std; class Solution {    public:    int getAns(vector& a) {       int ret = 0;       int n = a.size();       vector<int> v(n);       stack<int> st;       for (int i = 0; i < a.size(); i++) {          while (!st.empty() && a[st.top()] >= a[i])             st.pop();          if(!st.empty()) {             int prev = st.top();             v[i] += v[prev];             v[i] += a[i] * (i - prev);          }          else{             v[i] += a[i] * (i + 1);          }          st.push(i);       }       for (int i : v) {          ret += i;       }       return ret;    }    int solve(vector<vector<int>>& v) {       int ret = 0;       int n = v.size();       int m = n ? v[0].size() : 0;       vector<int> temp(m);       for (int i = 0; i < n; i++) {          for (int j = 0; j < m; j++) {             temp[j] = v[i][j] ? temp[j] + 1 : 0;          }          ret += getAns(temp);       }       return ret;    } }; int solve(vector<vector<int>>& matrix) {    return (new Solution())->solve(matrix); } main(){    vector<vector> matrix = {       {1, 1, 0},       {1, 1, 0},       {0, 0, 1}    };    cout << solve(matrix); }

Input

{{1, 1, 0},{1, 1, 0},{0, 0, 1}};

Output

10