Tìm diện tích ma trận con lớn nhất có số 1 nhiều hơn số 0 đúng 1 đơn vị trong C++

Trong bài toán này, chúng ta được cung cấp một ma trận 2-D kích thước n x n gồm các số nhị phân (0/1). Nhiệm vụ là viết chương trình tìm Diện tích ma trận con lớn nhất có số lượng 1 nhiều hơn số lượng 0 đúng 1 đơn vị.

Ví dụ minh họa

Đầu vào

bin[N][N] = { {0, 1, 0, 0},
              {1, 1, 0, 0},
              {1, 0, 1, 1},
              {0, 1, 0, 1} }

Đầu ra

9

Giải thích

Ma trận con: hàng 1-3, cột 0-2 là ma trận con lớn nhất có số 1 nhiều hơn số 0 đúng 1 đơn vị.
Số 0 = 4, Số 1 = 5

Phương pháp giải

Cách đơn giản: tìm tất cả ma trận con có thể từ ma trận và trả về diện tích lớn nhất. Cách này dễ nghĩ nhưng tốn nhiều thời gian, độ phức tạp O(n^4).

Cách hiệu quả hơn: cố định cột trái và cột phải của ma trận, sau đó tìm mảng con lớn nhất có số 0 nhiều hơn số 1 đúng 1 đơn vị. Ta tính tổng tại mỗi hàng và tích lũy. Để tìm diện tích lớn nhất có số 1 nhiều hơn số 0 đúng 1.

Chương trình minh họa

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

#define SIZE 10

int lenOfLongSubarr(int row[], int n, int& startInd, int& finishInd) {
    unordered_map<int, int> subArr;
    int sumVal = 0, maxSubArrLen = 0;
    
    for (int i = 0; i < n; i++) {
        sumVal += row[i];
        if (sumVal == 1) {
            startInd = 0;
            finishInd = i;
            maxSubArrLen = i + 1;
        } else if (subArr.find(sumVal) == subArr.end())
            subArr[sumVal] = i;
        
        if (subArr.find(sumVal - 1) != subArr.end()) {
            int currLen = (i - subArr[sumVal - 1]);
            if (maxSubArrLen < currLen) {
                startInd = subArr[sumVal - 1] + 1;
                finishInd = i;
                maxSubArrLen = currLen;
            }
        }
    }
    return maxSubArrLen;
}

int largestSubmatrix(int bin[SIZE][SIZE], int n) {
    int rows[n], maxSubMatArea = 0, currArea, longLen, startInd, finishInd;
    
    for (int left = 0; left < n; left++) {
        memset(rows, 0, sizeof(rows));
        for (int right = left; right < n; right++) {
            for (int i = 0; i < n; ++i) {
                if (bin[i][right] == 0)
                    rows[i] -= 1;
                else
                    rows[i] += 1;
            }
            longLen = lenOfLongSubarr(rows, n, startInd, finishInd);
            currArea = (finishInd - startInd + 1) * (right - left + 1);
            if ((longLen != 0) && (maxSubMatArea < currArea)) {
                maxSubMatArea = currArea;
            }
        }
    }
    return maxSubMatArea;
}

int main() {
    int bin[SIZE][SIZE] = {
        { 1, 0, 0, 1 },
        { 0, 1, 1, 1 },
        { 1, 0, 0, 0 },
        { 0, 1, 0, 1 }
    };
    int n = 4;
    cout << "Diện tích ma trận con lớn nhất có số 1 nhiều hơn số 0 đúng 1 là "
         << largestSubmatrix(bin, n);
    return 0;
}

Đầu ra

Diện tích ma trận con lớn nhất có số 1 nhiều hơn số 0 đúng 1 là 9