Tìm diện tích hình chữ nhật lớn nhất chỉ chứa 1 trong ma trận nhị phân bằng C++

Trong bài toán này, chúng ta được cung cấp một ma trận 2-D bin[][] kích thước n x m chỉ chứa các số nhị phân (0/1). Nhiệm vụ là viết chương trình tìm Diện tích hình chữ nhật lớn nhất trong ma trận nhị phân chỉ chứa 1 và trả về diện tích tối đa.

Ví dụ minh họa

Đầu vào

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

Đầu ra

12

Giải thích

Hình chữ nhật diện tích lớn nhất chỉ chứa 1:
1, 1, 1
1, 1, 1
1, 1, 1
1, 1, 1

Phương pháp giải

Để giải bài toán, ta cần tìm hình chữ nhật con lớn nhất chỉ chứa 1. Với mỗi hàng, ta tính diện tích hình chữ nhật tạo thành đến hàng hiện tại.

Diện tích đến hàng hiện tại được tính bằng cách tìm số lượng 1 liên tiếp đến phần tử hiện tại trong cột. Ta xét các phần tử có số lượng 1 lớn hơn hoặc bằng, tức là nếu tất cả khác nhau, ta lấy số nhỏ nhất. Hàng có diện tích lớn nhất sẽ là kết quả.

Chương trình minh họa

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

#define R 4
#define C 5

int calcAreaTillRow(int row[]) {
    stack<int> area1s;
    int tos;
    int maxArea = 0;
    int curArea = 0;
    int i = 0;
    
    while (i < C) {
        if (area1s.empty() || row[area1s.top()] <= row[i])
            area1s.push(i++);
        else {
            tos = row[area1s.top()];
            area1s.pop();
            curArea = tos * i;
            if (!area1s.empty())
                curArea = tos * (i - area1s.top() - 1);
            maxArea = max(curArea, maxArea);
        }
    }
    
    while (!area1s.empty()) {
        tos = row[area1s.top()];
        area1s.pop();
        curArea = tos * i;
        if (!area1s.empty())
            curArea = tos * (i - area1s.top() - 1);
        maxArea = max(curArea, maxArea);
    }
    return maxArea;
}

int calcmaxRecSubMat1(int bin[][C]) {
    int result = calcAreaTillRow(bin[0]);
    for (int i = 1; i < R; i++) {
        for (int j = 0; j < C; j++)
            if (bin[i][j])
                bin[i][j] += bin[i - 1][j];
        result = max(result, calcAreaTillRow(bin[i]));
    }
    return result;
}

int main() {
    int bin[][C] = {
        {1, 0, 1, 1, 1},
        {0, 1, 1, 1, 1},
        {0, 0, 1, 1, 1},
        {1, 1, 1, 1, 1}
    };
    cout << "Diện tích hình chữ nhật lớn nhất chỉ chứa 1 trong ma trận nhị phân là "
         << calcmaxRecSubMat1(bin);
    return 0;
}

Đầu ra

Diện tích hình chữ nhật lớn nhất chỉ chứa 1 trong ma trận nhị phân là 12