Tìm ô có tổng hình chữ nhật bằng nhau trong ma trận C++

Giới thiệu

Cho ma trận m×n. Tìm ô (i,j) sao cho: tổng hình chữ nhật từ (0,0) đến (i,j) + tổng hình chữ nhật từ (i,j) đến (m-1,n-1) = tổng các phần tử còn lại.

Tức là: Tổng 2 hình chữ nhật góc = Tổng phần tử còn lại = Tổng ma trận / 2

Ví dụ

Ma trận 4×4:

5  0  2  7
3  0  1  0
1  4  1  3
10 0  2  1

Ô (1,1) giá trị 0:

• Hình chữ nhật 1 (0,0)-(1,1): 5+0+3+0 = 8
• Hình chữ nhật 2 (1,1)-(3,3): 0+1+0+4+1+3+0+2+1 = 12
• Tổng = 8+12-0(trùng) = 20
• Tổng ma trận = 40 → 20 = 40/2 ✓

Ô (2,1) giá trị 4 cũng thỏa mãn.

Thuật toán: Prefix Sum 2D

Tính 2 ma trận tiền tố:

• aux1[i][j] = tổng từ (0,0) đến (i,j)
• aux2[i][j] = tổng từ (i,j) đến (m-1,n-1)

Tổng tại ô (i,j) = aux1[i][j] + aux2[i][j] - mat[i][j] (trừ phần trùng)

Mã nguồn hoàn chỉnh

#include <bits/stdc++.h>
using namespace std;

void findCellsWithEqualRectSum(vector> mat) {
    int m = mat.size();
    int n = mat[0].size();
    
    vector> aux1(m, vector(n));
    vector> aux2(m, vector(n));
    int totalSum = 0;
    
    // Khởi tạo
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            aux1[i][j] = aux2[i][j] = mat[i][j];
            totalSum += mat[i][j];
        }
    }
    
    // aux1: prefix sum từ (0,0)
    for (int i = 1; i < m; i++) aux1[i][0] += aux1[i-1][0];
    for (int j = 1; j < n; j++) aux1[0][j] += aux1[0][j-1];
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            aux1[i][j] += aux1[i-1][j] + aux1[i][j-1] - aux1[i-1][j-1];
        }
    }
    
    // aux2: suffix sum từ (m-1,n-1)
    for (int i = m-2; i >= 0; i--) aux2[i][n-1] += aux2[i+1][n-1];
    for (int j = n-2; j >= 0; j--) aux2[m-1][j] += aux2[m-1][j+1];
    for (int i = m-2; i >= 0; i--) {
        for (int j = n-2; j >= 0; j--) {
            aux2[i][j] += aux2[i+1][j] + aux2[i][j+1] - aux2[i+1][j+1];
        }
    }
    
    // Tìm ô thỏa mãn
    cout << "Cac o thoa man: ";
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int sum = aux1[i][j] + aux2[i][j] - mat[i][j];
            if (2 * sum == totalSum) {
                cout << "(" << i << "," << j << ") ";
            }
        }
    }
    cout << endl;
}

int main() {
    vector> mat = {
        {5, 0, 2, 7},
        {3, 0, 1, 0},
        {1, 4, 1, 3},
        {10, 0, 2, 1}
    };
    
    findCellsWithEqualRectSum(mat);
    return 0;
}

Kết quả chạy chương trình

Cac o thoa man: (1,1) (2,1)

Phân tích độ phức tạp

• Thời gian: O(m×n) - 3 lần duyệt ma trận
• Không gian: O(m×n) - 2 ma trận phụ

Tối ưu không gian O(1) thêm

Có thể tính aux1 tại chỗ trên mat (nếu cho phép sửa mat), hoặc chỉ dùng 1 mảng 1D rolling.

Kết luận

Bài toán ứng dụng Prefix Sum 2D (tiền tố 2 chiều) - kỹ thuật quan trọng cho truy vấn tổng vùng hình chữ nhật O(1) sau tiền xử lý O(mn).