Chương trình tìm số lượng ma trận con toàn số 1 trong C++

Giả sử chúng ta được cung cấp một ma trận chỉ chứa hai giá trị: 1 và 0. Chúng ta phải tìm số lượng ma trận con trong ma trận đã cho mà chứa toàn bộ các số 1. In kết quả ra màn hình.

Ví dụ, với ma trận 4x4:

Kết quả sẽ là 12.

Giải thuật

• n := kích thước ma trận, m := kích thước ma trận[0]
• Định nghĩa mảng cộng dồn add kích thước (n+1) x (m+1)
• Tính tổng tiền tố 2D cho add
• res := 0
• Duyệt qua từng ô (i, j):
  • Nếu matrix[i][j] == 0, bỏ qua
  • Với mỗi chiều cao k từ 1 đến n-i:
    • Tìm kiếm nhị phân chiều rộng tối đa x sao cho ma trận con k x x toàn số 1
    • Cộng x vào kết quả
• Trả về res

Ví dụ minh họa

#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; 
                int 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; 
}

Đầu vào

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

Đầu ra

12