Tìm số điểm "endless" trong ma trận C++

Giới thiệu

Cho ma trận mat[n][m] chỉ chứa 0 và 1. Điểm mat[i][j] gọi là "endless" nếu tất cả các phần tử bên dưới nó (cùng cột) và bên phải nó (cùng hàng) đều bằng 1.

Ví dụ minh họa

Đầu vào

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

Đầu ra

2

Giải thích

Phần tử mat[0][1] và mat[1][1] là endless.

Phương pháp giải: Quy hoạch động

Sử dụng hai ma trận DP: - rowDP[i][j]: số 1 liên tiếp bên phải từ mat[i][j] - colDP[i][j]: số 1 liên tiếp bên dưới từ mat[i][j]

Điểm (i,j) là endless nếu rowDP[i][j] == m-j và colDP[i][j] == n-i.

Chương trình minh họa

Lưu ý: Code mẫu trong nội dung gốc bị nhầm lẫn với bài toán "số ngày giữa hai ngày". Dưới đây là code đúng cho bài toán endless points:

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

int countEndlessPoints(vector>& mat) {
    int n = mat.size();
    if (n == 0) return 0;
    int m = mat[0].size();
    
    vector> rowDP(n, vector(m, 0));
    vector> colDP(n, vector(m, 0));
    
    // Tính rowDP: từ phải sang trái
    for (int i = 0; i < n; i++) {
        for (int j = m - 1; j >= 0; j--) {
            if (mat[i][j] == 1) {
                rowDP[i][j] = 1;
                if (j + 1 < m) rowDP[i][j] += rowDP[i][j+1];
            }
        }
    }
    
    // Tính colDP: từ dưới lên trên
    for (int j = 0; j < m; j++) {
        for (int i = n - 1; i >= 0; i--) {
            if (mat[i][j] == 1) {
                colDP[i][j] = 1;
                if (i + 1 < n) colDP[i][j] += colDP[i+1][j];
            }
        }
    }
    
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (mat[i][j] == 1 && rowDP[i][j] == m - j && colDP[i][j] == n - i)
                count++;
        }
    }
    return count;
}

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

Đầu ra

Number of endless points: 2