Hướng giải của Hình chữ nhật lớn nhất trong ma trận nhị phân

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

lời giải: Hình chữ nhất lớn nhất trong ma tran nhi phan

Phan tich

bài toán được giai bang cach ap dung thuat toan Largest Rectangle in Histogram cho tung hang cua ma tran.

Duyet tung hang tu tren xuong duoi:

  • Voi moi hang, cap nhất chieu cao cua cac cot: neu o hien tai la 1 thi tang chieu cao len 1, nguoc lai dat ve 0.
  • Ap dung thuat toan Largest Rectangle in Histogram de tìm hình chữ nhất toan 1 lớn nhất tai hang nay.

Do phuc tap: \(O(N \times M)\).

Ma nguon C++

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

long long largestRectangle(vector<int>& h) {
    stack<int> st;
    long long ans = 0;
    h.push_back(0);
    for (int i = 0; i < (int)h.size(); i++) {
        while (!st.empty() && h[st.top()] > h[i]) {
            long long height = h[st.top()]; st.pop();
            int left = st.empty() ? -1 : st.top();
            long long width = i - left - 1;
            ans = max(ans, height * width);
        }
        st.push(i);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];
    vector<int> h(m, 0);
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == 1) h[j]++;
            else h[j] = 0;
        }
        ans = max(ans, largestRectangle(h));
    }
    cout << ans << "\n";
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.