Решение задачи Фермер - 2 с Acmp

Без пояснения   Просмотров: 760


После решения задачи с пашней земли, фермер хочет построить на этой земле как можно больший по площади сарай прямоугольной формы. Но на его участке есть деревья и хозяйственные постройки, которые он не хочет никуда переносить. Для простоты представим ферму прямоугольной сеткой размера M×N. Каждое из деревьев и построек размещается в одном или нескольких узлах сетки. Сарай должен быть построен на свободных узлах сетки.

Помогите фермеру определить максимально возможную площадь сарая.

Код

#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
#include <bits/stdc++.h>
using namespace std;

int main()
{
    
    unsigned n, m;
    char tch;
    cin >> n >> m;
    vector< vector< unsigned short > > a;
    vector< unsigned short > t;

    for(unsigned i = 0; i < n; ++i) {
        t.clear();
        for(unsigned j = 0; j < m; ++j) {
            cin >> tch;
            t.push_back(tch - 48);
        }
        a.push_back(t);
    }
    int r = 0;
    vector< int > c(n + 1, 0);



    for(int x = m - 1; x >=0; --x) {
//        cout << "------- x = " << x << " -------\n";
        for(int y = 0; y < n; ++y)
            c[y] = a[y][x] ? c[y] + 1 : 0;

        //
        //cout << x << endl;
        //for(int i: c)
        //    cout << i << " ";
        //cout << endl;
        //

        stack< pair< int, int > > s;
        int w = 0;
        for (int y = 0; y <= n; ++y) {
//            cout << y << ":" << "w = " << w << " c[y] = " << c[y] << endl;
            if (c[y] > w) {
                s.push(make_pair(y, w));
                w = c[y];
            }
            if (c[y] < w) {
                int y0, w0;
                do {
                    y0 = s.top().first;
                    w0 = s.top().second;
                    s.pop();
                    if (w * (y - y0) > r)
                        r = w * (y - y0);
                    w = w0;
                } while (c[y] < w);
                w = c[y];
                if (w != 0)
                    s.push(make_pair(y0, w0));
            }
        }
//        cout << "r = " << r << endl;
    }
    cout << r;
    return 0;
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться