C ++中矩阵中连续的最长行

假设我们有一个二进制矩阵M，我们必须在该矩阵中找到连续的最长行。该线可以是水平，垂直，对角线或反对角线。

所以，如果输入像

那么输出将是3

为了解决这个问题，我们将遵循以下步骤-

• ret：= 0

• n：= M行

• m：= M的列

• 定义一个nxmx 4阶的3D数组dp

• 对于初始化i：= 0，当i <m时，更新（将i增加1），执行-

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

• ret：= ret和dp [0，i，j]的最大值

• 对于初始化j：= 0，当j <4时更新（将j增加1），执行-

• 对于初始化j：= 0，当j <m时，更新（将j增加1），执行-

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

• ret：= ret和dp [0，j，1]的最大值

• 如果M [0，j]为非零且j> 0，则-

• 对于初始化i：= 1，当i <n时，更新（将i增加1），-

• dp [i，j，0]：=（如果M [i，j]为非零，则1 + dp [i-1，j，0]，否则为0）

• 如果j> 0，则-

• 除此以外

• 如果j + 1 <m，则-

• 除此以外

• 对于初始化k：= 0，当k <4时，更新（将k增加1），执行-

• 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]

• dp [i，j，3]：=（如果M [i，j]不为零，则dp [i-1，j + 1，3] + 1，否则为0）

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

• ret：= ret和dp [i，j，k]的最大值

• 对于初始化j：= 0，当j <m时，更新（将j增加1），执行-

• 返回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