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