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

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


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

Необходимо помочь фермеру определить максимальную площадь пашни.

Код

#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
 
int main()
{
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    unsigned n;
    char tch;
    fin >> n;
    vector< vector< unsigned short > > m;
    vector< unsigned short > t;
    unsigned maxK = 0;
 
    for(unsigned i = 0; i < n; ++i) {
        t.clear();
        int k = 0;
        for(unsigned j = 0; j < n; ++j) {
            fin >> tch;
            t.push_back(tch - 48);
            if(tch - 48)
                maxK = 1;
        }
        m.push_back(t);
    }
 
 
    for(int i = n - 2; i >= 0; --i) {
        for(int j = n - 2; j >= 0; --j) {
            int lmin = min(m.at(i).at(j + 1),
                           min(m.at(i + 1).at(j), m.at(i + 1).at(j + 1)));
            if(m.at(i).at(j) && lmin) {
                m.at(i).at(j) = lmin + 1;
                if(maxK < m.at(i).at(j))
                    maxK = m.at(i).at(j);
            }
        }
    }
 
    fout << maxK * maxK;
 
    return 0;
}

         

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



Комментарии

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