หาจำนวน Endless Points ในเมทริกซ์ด้วย C++

ภาพรวมปัญหา

ได้รับเมทริกซ์ mat[n][m] ประกอบด้วย 0 และ 1 จุด (i,j) ถือว่าเป็น "Endless Point" ถ้า:

• ทุกเซลล์ด้านล่างในคอลัมน์เดียวกันเป็น 1: mat[i+1][j] ... mat[n-1][j] = 1
• ทุกเซลล์ด้านขวาในแถวเดียวกันเป็น 1: mat[i][j+1] ... mat[i][m-1] = 1

ตัวอย่าง

อินพุต

mat[][] = { {0, 0},
            {1, 1} }

เอาต์พุต

2

คำอธิบาย

mat[0][1] และ mat[1][1] เป็น endless points

วิธีแก้ปัญหา

วิธีที่ 1: Brute Force - O(n×m×(n+m))

ตรวจสอบทุกเซลล์โดยวนดูด้านล่างและด้านขวา

วิธีที่ 2: Dynamic Programming - O(n×m) ⭐

สร้าง 2 ตาราง DP:

• rowDP[i][j]: จำนวน 1 ติดต่อกันไปทางขวาจาก (i,j) รวมตัวเอง
• colDP[i][j]: จำนวน 1 ติดต่อกันไปทางล่างจาก (i,j) รวมตัวเอง

เซลล์ (i,j) เป็น endless ถ้า rowDP[i][j] == m-j และ colDP[i][j] == n-i

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

#include <iostream>
#include <vector>
using namespace std;

int countEndlessPoints(vector<vector<int>>& mat) {
    int n = mat.size();
    if (n == 0) return 0;
    int m = mat[0].size();
    
    vector<vector<int>> rowDP(n, vector<int>(m, 0));
    vector<vector<int>> colDP(n, vector<int>(m, 0));
    
    // เติม rowDP (จากขวาไปซ้าย)
    for (int i = 0; i < n; i++) {
        for (int j = m - 1; j >= 0; j--) {
            if (mat[i][j] == 1) {
                rowDP[i][j] = 1 + (j + 1 < m ? rowDP[i][j + 1] : 0);
            }
        }
    }
    
    // เติม colDP (จากล่างขึ้นบน)
    for (int j = 0; j < m; j++) {
        for (int i = n - 1; i >= 0; i--) {
            if (mat[i][j] == 1) {
                colDP[i][j] = 1 + (i + 1 < n ? colDP[i + 1][j] : 0);
            }
        }
    }
    
    // นับ endless points
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (rowDP[i][j] == m - j && colDP[i][j] == n - i) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    vector<vector<int>> mat = { {0, 0}, {1, 1} };
    cout << "Number of endless points: " << countEndlessPoints(mat);
    return 0;
}

เอาต์พุต

Number of endless points: 2

สรุป

DP Approach ลด Complexity จาก O(n×m×(n+m)) เป็น O(n×m) โดยใช้ตารางสะสมผลรวม

หมายเหตุ: โค้ดต้นฉบับมีส่วนที่ไม่เกี่ยวข้อง (โค้ดนับวันระหว่างวันที่) ซึ่งได้ตัดออกแล้ว