C ++中矩阵中连续的最长行
假设我们有一个二进制矩阵M，我们必须在该矩阵中找到连续的最长行。该线可以是水平，垂直，对角线或反对角线。
所以，如果输入像
那么输出将是3
为了解决这个问题，我们将遵循以下步骤-
ret：=0
n：=M行
m：=M的列
定义一个nxmx4阶的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