Query จำนวน Binary Sub-matrices ขนาดกำหนดใน C++

ในปัญหานี้ กำหนดให้มี Binary Matrix bin[][] ขนาด n×m ภารกิจคือตอบคำถาม (Query) ทั้งหมด q คำถาม สำหรับ Query(x, y) ต้องหาจำนวน Sub-matrix ขนาด x×x ที่ทุกอิลิเมนต์มีค่าเป็น y (0 หรือ 1)

คำอธิบายปัญหา

นับจำนวน Sub-matrix ขนาดที่กำหนด ที่ประกอบด้วยบิตเดียวกันทั้งหมด (ทั้ง 0 หรือทั้ง 1)

ตัวอย่าง

Input: n = 3, m = 4
bin[][] = {{1, 1, 0, 1}, {1, 1, 1, 0}, {0, 1, 1, 1}}
q = 1, q1 = (2, 1)
Output: 2

คำอธิบาย: Sub-matrix 2×2 ที่เป็น 1 ทั้งหมด มี 2 ตัว

วิธีแก้: Dynamic Programming

สร้างตาราง DP[][] เก็บขนาด Sub-matrix สูงสุดที่สิ้นสุดที่ (i,j) และมีค่าเหมือนกันทั้งหมด

• Case 1: i=0 หรือ j=0 → DP[i][j] = 1
• Case 2: ถ้า 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-1][j-1], DP[i][j-1]) + 1
• มิฉะนั้น → DP[i][j] = 1

นับความถี่ของแต่ละขนาดสำหรับ 0 และ 1 แยกกัน แล้วสะสมสะสม (cumulative) เพื่อตอบ Query ได้ใน O(1)

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

#include <iostream>
using namespace std;

#define N 3
#define M 4

int min(int a, int b, int c) {
    if (a <= b && a <= c) return a;
    else if (b <= a && b <= c) return b;
    else return c;
}

int solveQuery(int n, int m, int bin[N][M], int x, int y) {
    int DP[n][m], max = 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] = min(DP[i-1][j], DP[i-1][j-1], DP[i][j-1]) + 1;
                if (max < DP[i][j]) max = DP[i][j];
            } else
                DP[i][j] = 1;
        }
    }
    
    int zeroFrequency[n+m] = {0}, oneFrequency[n+m] = {0};
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (bin[i][j] == 0) zeroFrequency[DP[i][j]]++;
            else oneFrequency[DP[i][j]]++;
    
    for (int i = max - 1; i >= 0; i--) {
        zeroFrequency[i] += zeroFrequency[i+1];
        oneFrequency[i] += oneFrequency[i+1];
    }
    
    return (y == 0) ? zeroFrequency[x] : oneFrequency[x];
}

int main() {
    int n = 3, m = 4;
    int mat[N][M] = {{1, 1, 0, 1}, {1, 1, 1, 0}, {0, 1, 1, 1}};
    int Q = 2;
    int query[Q][2] = {{2, 1}, {1, 0}};
    
    for (int i = 0; i < Q; i++) {
        cout << "For Query " << (i+1) << ": The number of Binary sub-matrices of Given size is "
             << solveQuery(n, m, mat, query[i][0], query[i][1]) << "\n";
    }
    return 0;
}

ผลลัพธ์

For Query 1: The number of Binary sub-matrices of Given size is 2
For Query 2: The number of Binary sub-matrices of Given size is 3