Truy vấn số ma trận con nhị phân kích thước cho trước trong C++

Cho ma trận nhị phân bin[n][m] và q truy vấn. Mỗi truy vấn (x, y): đếm số ma trận con vuông kích thước x*x toàn là giá trị y (0 hoặc 1).

Mô tả bài toán

Đếm ma trận con vuông kích thước cho trước gồm toàn 0 hoặc toàn 1.

Ví dụ

Đầu vào: n=3, m=4

bin = {{1,1,0,1}, {1,1,1,0}, {0,1,1,1}}
q = 1, truy vấn: (2, 1)

Đầu ra: 2

Giải thích: 2 ma trận con 2x2 toàn 1.

Giải pháp: Quy hoạch động (Dynamic Programming)

DP[i][j] = kích thước lớn nhất ma trận vuông toàn giá trị giống nhau có góc dưới-phải tại (i,j).

Công thức:

• Nếu i=0 hoặc j=0: DP[i][j] = 1
• Nếu bin[i][j] == bin[i-1][j] == bin[i][j-1] == bin[i-1][j-1]: DP[i][j] = min(DP[i-1][j], DP[i][j-1], DP[i-1][j-1]) + 1
• Ngược lại: DP[i][j] = 1

Sau đó tính tần suất tần suất cho mỗi kích thước k cho giá trị 0 và 1. Dùng mảng prefix sum để trả lời truy vấn O(1).

Ví dụ mã nguồn

#include <iostream>
using namespace std;

#define N 3
#define M 4

int min3(int a, int b, int c) {
    return min(a, min(b, c));
}

int giaiTruyVan(int n, int m, int bin[N][M], int x, int y) {
    int dp[N][M], maxK = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i == 0 || j == 0) dp[i][j] = 1;
            else if (bin[i][j] == bin[i-1][j] && bin[i][j] == bin[i][j-1] && bin[i][j] == bin[i-1][j-1]) {
                dp[i][j] = min3(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1;
                maxK = max(maxK, dp[i][j]);
            } else dp[i][j] = 1;
        }
    }
    
    vector<int> freq0(n+m+1, 0), freq1(n+m+1, 0);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (bin[i][j] == 0) freq0[dp[i][j]]++;
            else freq1[dp[i][j]]++;
    
    for (int k = maxK-1; k >= 0; k--) {
        freq0[k] += freq0[k+1];
        freq1[k] += freq1[k+1];
    }
    
    return (y == 0) ? freq0[x] : freq1[x];
}

int main() {
    int bin[N][M] = {{1,1,0,1}, {1,1,1,0}, {0,1,1,1}};
    int queries[2][2] = {{2,1}, {1,0}};
    for (int i = 0; i < 2; i++)
        cout << "Truy vấn " << i+1 << ": " << giaiTruyVan(N, M, bin, queries[i][0], queries[i][1]) << "\n";
    return 0;
}

Kết quả

Truy vấn 1: 2
Truy vấn 2: 3