C++で合計してターゲットになる部分行列の数

行列とターゲット値があるとすると、合計がターゲットと同じである空でないサブマトリックスの数を見つける必要があります。ここで、部分行列[（x1、y1）、（x2、y2）]は、範囲x1とx2にxがあり、範囲y1とy2にyがあるすべてのセルmatrix[x][y]のセットです。 2つの部分行列[（x1、y1）、（x2、y2）]と[（x1'、y1'）、（x2'、y2'）]は、座標が異なる場合は異なります。たとえば、x1が異なる場合などです。 x1'と同じ。

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

target =0の場合、出力は4になります。これは、0のみを含む4つの1x1サブマトリックスが原因です。

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

• ans：=0

• col：=列数

• 行：=行数

• 初期化i：=0の場合、i <行の場合、更新（iを1増やします）、実行-

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

    • matrix [i、j]：=matrix [i、j] + matrix [i、j-1]

• 1つのマップを定義するm

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

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

    • マップをクリアするm

    • m [0]：=1

    • 合計：=0

  • 初期化k：=0の場合、k <行の場合、更新（kを1増やします）、実行-

    • 現在：=マトリックス[k、j]

    • i --1> =0の場合、-

      • current：=current --matrix [k、i-1]

    • 合計：=合計+現在

    • ans：=ans + m [target --sum]

    • m[-sum]を1増やします

• ansを返す

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

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int numSubmatrixSumTarget(vector<vector<int>>& matrix, int
   target) {
      int ans = 0;
      int col = matrix[0].size();
      int row = matrix.size();
      for(int i = 0; i < row; i++){
         for(int j = 1; j < col; j++){
            matrix[i][j] += matrix[i][j - 1];
         }
      }
      unordered_map <int, int> m;
      for(int i = 0; i < col; i++){
         for(int j = i; j < col; j++){
            m.clear();
            m[0] = 1;
            int sum = 0;
            for(int k = 0; k < row; k++){
               int current = matrix[k][j];
               if(i - 1 >= 0)current -= matrix[k][i - 1];
               sum += current;
               ans += m[target - sum];
               m[-sum]++;
            }
         }
      }
      return ans;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,1,0},{1,1,1},{0,1,0}};
   cout << (ob.numSubmatrixSumTarget(v, 0));
}

入力

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

出力

4