Dòng liên tiếp 1 dài nhất trong ma trận trong C++

Giới thiệu

Cho ma trận nhị phân. Tìm độ dài đường liên tiếp các số 1 dài nhất theo 4 hướng: ngang, dọc, chéo chính, chéo phụ.

Thuật toán: Quy hoạch động 3D

dp[i][j][k] = độ dài đường 1 kết thúc tại (i,j) theo hướng k:

• k=0: dọc (từ trên xuống)
• k=1: ngang (từ trái sang)
• k=2: chéo chính (từ trên-trái)
• k=3: chéo phụ (từ trên-phải)

Cập nhật:

dp[i][j][0] = M[i][j] ? 1 + dp[i-1][j][0] : 0
dp[i][j][1] = M[i][j] ? 1 + dp[i][j-1][1] : 0
dp[i][j][2] = M[i][j] ? 1 + dp[i-1][j-1][2] : 0
dp[i][j][3] = M[i][j] ? 1 + dp[i-1][j+1][3] : 0

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int longestLine(vector>& M) {
        int n = M.size(), m = n ? M[0].size() : 0;
        if (!m) return 0;
        vector>> dp(n, vector>(m));
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (M[i][j] == 0) continue;
                dp[i][j][0] = 1 + (i ? dp[i-1][j][0] : 0);
                dp[i][j][1] = 1 + (j ? dp[i][j-1][1] : 0);
                dp[i][j][2] = 1 + (i && j ? dp[i-1][j-1][2] : 0);
                dp[i][j][3] = 1 + (i && j+1> M = {{0,1,1,0},{0,1,1,0},{0,0,0,1}};
    cout << ob.longestLine(M); // Output: 3
    return 0;
}

Phân tích

• Thời gian: O(n*m).
• Không gian: O(n*m) (có thể tối ưu O(m) chỉ giữ hàng trước).

LeetCode 562 "Longest Line of Consecutive One in Matrix".