C++ですべてのものを含む正方形の部分行列を数える

サイズがmxnのバイナリ行列を想定します。すべて1で、正方形の部分行列の数を数える必要があります。したがって、行列が-

したがって、15個の正方形があります。単一のものの10の正方形、4つのものの4つの正方形、および9つのものの1つの正方形。

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

• set ans：=0、n：=行数およびm：=列数
• 0からm–1の範囲のiの場合
  • ans：=ans + matrix [n – 1、i]
• 0からn–1の範囲のiの場合
  • ans：=ans + matrix [i、m – 1]
• ans：=ans – matrix [n – 1、m-1]
• n –2から0までの範囲のiの場合
  • m –2から0までの範囲のjの場合
    • matrix [i、j] =1の場合、
      • matrix [i、j]：=1 +最小値（matrix [i + 1、j + 1]、matrix [i、j + 1]、matrix [i + 1、j]）
    • それ以外の場合、matrix [i、j]：=0
    • ans：=ans + matrix [i、j]
• 回答を返す

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

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int countSquares(vector<vector<int>>& matrix) {
      int ans = 0;
      int n = matrix.size();
      int m = matrix[0].size();
      for(int i = 0; i < m; i++)ans += matrix[n-1][i];
      for(int i = 0; i < n; i++)ans += matrix[i][m-1];
      ans -= matrix[n-1][m-1];
      for(int i = n - 2;i >= 0; i--){
         for(int j = m-2 ;j >= 0; j--){
            matrix[i][j] = matrix[i][j] == 1? 1 + min({matrix[i+1][j+1],matrix[i] [j+1],matrix[i+1][j]}) : 0;
            ans += matrix[i][j];
         }
      }
      return ans;
   }
};
main(){
   vector<vector<int>> v = {{0,1,1,1},{1,1,1,1},{0,1,1,1}};
   Solution ob;
   cout << (ob.countSquares(v));
}

入力

[[0,1,1,1],
[1,1,1,1],
[0,1,1,1]]

出力

15