C++で指定された行列の1の正方形のサブ行列の数を数えるプログラム

2次元のバイナリ行列があるとすると、すべて1の部分行列の総数を見つける必要があります。

したがって、入力が次のような場合

その場合、出力は10になります。これは、1 x 1行列が5つ、2x1行列が2つあるためです。 2つの1x2行列。そして、1つの2x2マトリックス。

これを解決するには、次の手順に従います-

• 関数getAns（）を定義します。これは、配列a、

  を取ります。

• ret：=0

• n：=a

  のサイズ

• サイズnの配列vを定義します

• 1つのスタックstを定義する

• 初期化i：=0の場合、i

  • 一方（stは空ではなく、a[stの最上位要素]>=a [i]）、do-

    • stからポップ

  • stが空でない場合、-

    • prev：=stの最上位要素

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

    • v [i]：=v [i] + a [i] *（i-prev）

  • それ以外の場合

    • v [i]：=v [i] + a [i] *（i + 1）

  • iをstに挿入

• vの各iについて-

  • ret：=ret + i

• retを返す

• メインの方法から、次のようにします-

• ret：=0

• n：=vのサイズ

• m：=（nがゼロ以外の場合、v [0]のサイズ、それ以外の場合は0）

• サイズmのアレイ温度を定義します

• 初期化i：=0の場合、i

  • 初期化j：=0の場合、j

    • temp [j]：=（v [i、j]がゼロ以外の場合、temp [j] + 1、それ以外の場合は0）

  • ret：=ret + getAns（temp）

• retを返す

例

理解を深めるために、次の実装を見てみましょう-

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

入力

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

出力

10