Longest Line of Consecutive One in Matrix – หาเส้น 1 ต่อเนื่องที่ยาวที่สุดใน C++

ปัญหา: Longest Line of Consecutive One in Matrix

กำหนด Binary Matrix M หา ความยาวเส้น 1 ต่อเนื่องที่ยาวที่สุด ทิศทาง: แนวนอน, แนวตั้ง, แนวทแยงมุม, แนวทแยงมุมตรงข้าม

ตัวอย่าง

Matrix:

0 1 1 0
0 1 1 0
0 0 0 1

Output: 3 (แนวตั้งคอลัมน์ 1: 1,1,1 หรือแนวนอนแถว 0: 1,1)

แนวทางแก้ปัญหา: 3D Dynamic Programming

State

dp[i][j][dir] = ความยาวเส้น 1 ต่อเนื่องจบที่ (i,j) ในทิศทาง dir

• dir=0: Vertical (↑)
• dir=1: Horizontal (←)
• dir=2: Diagonal (↖)
• dir=3: Anti-diagonal (↗)

Transitions

if M[i][j] == 1:
    dp[i][j][0] = 1 + dp[i-1][j][0]           // vertical
    dp[i][j][1] = 1 + dp[i][j-1][1]           // horizontal
    dp[i][j][2] = 1 + dp[i-1][j-1][2]         // diagonal
    dp[i][j][3] = 1 + dp[i-1][j+1][3]         // anti-diagonal
else:
    dp[i][j][*] = 0

ตัวอย่างโค้ด C++

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

class Solution {
public:
    int longestLine(vector<vector<int>>& M) {
        if (M.empty()) return 0;
        int n = M.size(), m = M[0].size();
        vector<vector<array<int,4>>> dp(n, vector<array<int,4>>(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 > 0 ? dp[i-1][j][0] : 0);
                dp[i][j][1] = 1 + (j > 0 ? dp[i][j-1][1] : 0);
                dp[i][j][2] = 1 + (i > 0 && j > 0 ? dp[i-1][j-1][2] : 0);
                dp[i][j][3] = 1 + (i > 0 && j+1 < m ? dp[i-1][j+1][3] : 0);

                for (int k = 0; k < 4; k++)
                    ans = max(ans, dp[i][j][k]);
            }
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> M = {{0,1,1,0},{0,1,1,0},{0,0,0,1}};
    cout << ob.longestLine(M); // 3
    return 0;
}

ความซับซ้อน

• เวลา: O(n × m)
• พื้นที่: O(n × m) – สามารถลดเป็น O(m) ได้โดยเก็บแค่แถวก่อนหน้า

Space Optimized (O(m))

vector<array<int,4>> prev(m), curr(m);
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (M[i][j]) {
            curr[j][0] = 1 + prev[j][0];
            curr[j][1] = 1 + (j > 0 ? curr[j-1][1] : 0);
            curr[j][2] = 1 + (j > 0 ? prev[j-1][2] : 0);
            curr[j][3] = 1 + (j+1 < m ? prev[j+1][3] : 0);
            // update ans
        } else {
            curr[j] = {0,0,0,0};
        }
    }
    swap(prev, curr);
}

ข้อสังเกต

• LeetCode 562
• DP 4 ทิศทาง ครอบคลุมทุกเส้นตรงในเมทริกซ์
• Anti-diagonal (↗) ต้องเข้าถึง prev[j+1] → ใช้ prev row
• โค้ดต้นฉบับมีการ initialize แถวแรกแยกต่างหาก – วิธีนี้รวมในลูปเดียวได้