与えられた行列がC++で同じ値のk×kの2乗を持つkを見つけるプログラム

2d行列があるとすると、すべての要素に同じ値が含まれている最大のk×k部分行列を見つけてから、kの値を見つける必要があります。

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

値5の3×3の正方行列があるため、出力は3になります。

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

• n：=行列の行数

• m：=行列の列数

• サイズ（n x m）の2D配列dpを1つ定義し、1で埋めます

• ret：=1

• 初期化i：=n --1の場合、i> =0の場合、更新（iを1つ減らす）、実行-

  • 初期化j：=m -1の場合、j> =0の場合、更新（jを1つ減らす）、実行-

    • val：=inf

    • i +1

      • val：=最小のdp [i + 1、j]およびval

    • それ以外の場合

      • val：=0

    • j + 1

      • val：=最小のdp [i、j+1]およびval

    • それ以外の場合

      • val：=0

    • i +1

      • val：=最小のdp [i + 1、j+1]およびval

    • それ以外の場合

      • val：=0

    • valがinfと同じ場合、-

      • 次の部分を無視し、次の反復にスキップします

    • dp [i、j]：=dp [i、j] + val

      • ret：=retとdp[i、j]

        の最大値

• retを返す

例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(vector<vector<int>>& v) {
      int n = v.size();
      int m = v[0].size();
      vector<vector<int>> dp(n, vector<int>(m, 1));
      int ret = 1;
      for (int i = n - 1; i >= 0; i--) {
         for (int j = m - 1; j >= 0; j--) {
            int val = INT_MAX;
            if (i + 1 < n && v[i + 1][j] == v[i][j]) {
               val = min(dp[i + 1][j], val);
            }
            else {
               val = 0;
            }
            if (j + 1 < m && v[i][j + 1] == v[i][j]) {
               val = min(dp[i][j + 1], val);
            }
            else {
               val = 0;
            }
            if (i + 1 < n && j + 1 < m && v[i + 1][j + 1] == v[i][j]) {
               val = min(dp[i + 1][j + 1], val);
            }
            else {
               val = 0;
            }
            if (val == INT_MAX)
               continue;
               dp[i][j] += val;
               ret = max(ret, dp[i][j]);
            }
         }
         return ret;
      }
};
int solve(vector<vector<int>>& matrix) {
   return (new Solution())->solve(matrix);
}
int main(){
   vector<vector<int>> matrix = {
      {1, 1, 8, 3},
      {1, 5, 5, 5},
      {2, 5, 5, 5},
      {4, 5, 5, 5}
   };
   cout << solve(matrix);
}

入力

{ {1, 1, 8, 3}, {1, 5, 5, 5}, {2, 5, 5, 5}, {4, 5, 5,
5} };

出力

3