โปรแกรมหาจำนวนซับแมทริกซ์ที่เป็น 1 ทั้งหมดใน C++

สมมติว่าเราได้รับแมทริกซ์ที่มีค่าแค่ 0 และ 1 เราต้องหาจำนวนซับแมทริกซ์ที่ประกอบด้วย 1 เท่านั้น

เช่น หากอินพุตเป็นแมทริกซ์ 4x4 ดังนี้:

ผลลัพธ์จะเป็น 12

ขั้นตอนการแก้ปัญหา

• n := จำนวนแถว, m := จำนวนคอลัมน์
• สร้างอาเรย์ 2 มิติ add ขนาด (n+1) x (m+1) สำหรับ Prefix Sum 2D
• คำนวณ add[i+1][j+1] = matrix[i][j] + add[i][j+1] + add[i+1][j] - add[i][j]
• res := 0
• วนลูปทุกเซลล์ (i, j) ที่เป็น 1:
  • วนลูปความสูง k จาก 1 ถึง n-i:
    • ใช้ Binary Search หาความกว้างสูงสุด x ที่ทำให้ซับแมทริกซ์ k x x เป็น 1 ทั้งหมด
    • ตรวจสอบด้วย Prefix Sum: cur = add[i+k][j+x] - add[i][j+x] - add[i+k][j] + add[i][j]
    • ถ้า cur == k * x แสดงว่าเป็นซับแมทริกซ์ที่ถูกต้อง
    • res += r (ความกว้างสูงสุดที่พบ)
• คืนค่า res

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

#include <bits/stdc++.h> using namespace std; int solve(vector<vector<int>>& matrix) {    int n = matrix.size();    int m = matrix[0].size();    int add[n + 1][m + 1];    memset(add, 0, sizeof(add));    for (int i = 0; i < n; i++) {       for (int j = 0; j < m; j++) {          add[i + 1][j + 1] += matrix[i][j];          add[i + 1][j + 1] += add[i][j + 1];          add[i + 1][j + 1] += add[i + 1][j];          add[i + 1][j + 1] -= add[i][j];       }    }    int res = 0;    for (int i = 0; i < n; i++) {       for (int j = 0; j < m; j++) {          if (!matrix[i][j]) continue;          for (int k = 1; k <= (n - i); k++) {             int p = 0, q = m - j, r;             while (p <= q) {                int x = (p + q) / 2;                int a = k * x;                int cur = add[i + k][j + x] - add[i][j + x] - add[i + k][j] + add[i][j];                if (cur == a) { r = x; p = x + 1; } else q = x - 1;             }             if (r == 0) break;             res += r;           }       }    }    return res; } int main() {    vector<vector<int>> mat = {{0, 0, 1, 0}, {0, 1, 0, 0}, {0, 1, 0, 1}, {1, 1, 0, 1}}; cout << solve(mat) << endl; return 0; }

อินพุต

{{0, 0, 1, 0}, {0, 1, 0, 0}, {0, 1, 0, 1}, {1, 1, 0, 1}}

เอาต์พุต

12