C++のマトリックス内の連続する1つの最長行

1つのバイナリ行列Mがあるとすると、その行列で連続するものの最長の行を見つける必要があります。線は、水平、垂直、対角、反対角のいずれかになります。

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

その場合、出力は3

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

• ret：=0

• n：=Mの行

• m：=Mの列

• 次数nxmx4の3D配列dpを1つ定義します

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

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

    • dp [0、i、j]：=M [0、i]

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

      の最大値

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

  • M [0、j]がゼロ以外で、j> 0の場合、-

    • dp [0、j、1]：=1 + dp [0、j-1、1]

    • ret：=retとdp[0、j、1]

      の最大値

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

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

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

    • j> 0の場合、-

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

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

    • それ以外の場合

      • dp [i、j、1]：=M [i、j]

      • dp [i、j、2]：=M [i、j]

    • j + 1

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

    • それ以外の場合

      • dp [i、j、3]：=M [i、j]

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

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

        の最大値

• retを返す

例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int longestLine(vector<vector<int>>& M) {
      int ret = 0;
      int n = M.size();
      int m = !n ? 0 : M[0].size();
      vector<vector<vector<int> > > dp(n, vector<vector<int> >(m, vector<int>(4)));
      for (int i = 0; i < m; i++) {
         for (int j = 0; j < 4; j++) {
            dp[0][i][j] = M[0][i];
            ret = max(ret, dp[0][i][j]);
         }
      }
      for (int j = 0; j < m; j++) {
         if (M[0][j] && j > 0) {
            dp[0][j][1] = 1 + dp[0][j - 1][1];
            ret = max(ret, dp[0][j][1]);
         }
      }
      for (int i = 1; i < n; i++) {
         for (int j = 0; j < m; j++) {
            dp[i][j][0] = M[i][j] ? 1 + dp[i - 1][j][0] : 0;
            if (j > 0) {
               dp[i][j][1] = M[i][j] ? dp[i][j - 1][1] + 1 : 0;
               dp[i][j][2] = M[i][j] ? dp[i - 1][j - 1][2] + 1 : 0;
            }
            else {
               dp[i][j][1] = M[i][j];
               dp[i][j][2] = M[i][j];
            }
            if (j + 1 < m) {
               dp[i][j][3] = M[i][j] ? dp[i - 1][j + 1][3] + 1 : 0;
            }
            else {
               dp[i][j][3] = M[i][j];
            }
            for (int k = 0; k < 4; k++) {
               ret = max(ret, dp[i][j][k]);
            }
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,1,1,0},{0,1,1,0},{0,0,0,1}};
   cout << (ob.longestLine(v));
}

入力

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

出力

3