พิมพ์เซลล์ที่มีผลรวมสี่เหลี่ยมผืนผ้าเท่ากันในเมทริกซ์ใน C++

บทนำ

โจทย์: หาเซลล์ (i,j) ในเมทริกซ์ ที่ผลรวมของ Submatrix (0,0) ถึง (i,j) + Submatrix (i,j) ถึง (m-1,n-1) เท่ากับผลรวมของเซลล์ที่เหลือทั้งหมด

เงื่อนไข

Sum(0,0 to i,j) + Sum(i,j to m-1,n-1) - mat[i][j] = TotalSum / 2 (ลบ mat[i][j] เพราะนับซ้ำ)

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

1. สร้าง Aux1[i][j] = Prefix Sum จาก (0,0) ถึง (i,j)
2. สร้าง Aux2[i][j] = Suffix Sum จาก (i,j) ถึง (m-1,n-1)
3. คำนวณ TotalSum ของเมทริกซ์ทั้งหมด
4. เช็คทุกเซลล์: ถ้า TotalSum == 2 × (Aux1[i][j] + Aux2[i][j] - mat[i][j]) → พิมพ์ (i,j)

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

#include <iostream>
using namespace std;

#define R 4
#define C 4

void findCellWithSameRectSum(int mat[R][C]) {
    int m = R, n = C;
    int aux1[m][n], aux2[m][n];
    int matSum = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            aux2[i][j] = aux1[i][j] = mat[i][j];
            matSum += mat[i][j];
        }
    }
    for (int i = 1; i < m; i++) {
        aux1[i][0] += aux1[i-1][0];
        aux2[m-i-1][n-1] += aux2[m-i][n-1];
    }
    for (int j = 1; j < n; j++) {
        aux1[0][j] += aux1[0][j-1];
        aux2[m-1][n-j-1] += aux2[m-1][n-j];
    }
    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[m-i-1][n-j-1] += aux2[m-i][n-j-1] + aux2[m-i-1][n-j] - aux2[m-i][n-j];
        }
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (matSum == 2 * (aux1[i][j] + aux2[i][j] - mat[i][j]))
                cout << "(" << i << ", " << j << ")\t";
}

int main() {
    int mat[R][C] = {{5, 0, 2, 7}, {3, 0, 1, 0}, {1, 4, 1, 3}, {10, 0, 2, 1}};
    cout << "The cells with same rectangular sums in a matrix is \n";
    findCellWithSameRectSum(mat);
    return 0;
}

ผลลัพธ์

The cells with same rectangular sums in a matrix is
(1, 1)       (2, 1)

คำอธิบาย

เซลล์ (1,1) และ (2,1) เป็นจุดที่แบ่งเมทริกซ์ได้ 2 ส่วนเท่ากัน (20 = 20)

สรุป

Prefix Sum 2D + Suffix Sum 2D แก้ปัญหา Submatrix Sum แบบ O(1) ต่อ Query หลัง Preprocessing O(mn)