資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中矩陣中連續 1 的最長線
假設我們有一個二進位制矩陣 M，我們需要找到該矩陣中連續 1 的最長線。這條線可以是水平的、垂直的、對角線的或反對角線的。
因此，如果輸入類似於
| 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 |
則輸出將為 3
為了解決這個問題，我們將遵循以下步驟：
ret := 0
n := M 的行數
m := M 的列數
定義一個 3D 陣列 dp，其階數為 n x m x 4
用於初始化 i := 0，當 i < m 時，更新（i 增加 1），執行：
用於初始化 j := 0，當 j < 4 時，更新（j 增加 1），執行：
dp[0, i, j] := M[0, i]
ret := ret 和 dp[0, i, j] 中的最大值
用於初始化 j := 0，當 j < m 時，更新（j 增加 1），執行：
如果 M[0, j] 不為零且 j > 0，則：
dp[0, j, 1] := 1 + dp[0, j - 1, 1]
ret := ret 和 dp[0, j, 1] 中的最大值
用於初始化 i := 1，當 i < n 時，更新（i 增加 1），執行：
用於初始化 j := 0，當 j < m 時，更新（j 增加 1），執行：
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 < m，則：
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
306 次瀏覽
