Задача "Фермер"

@Jacky09 · Регистрация: 15.09.2013

Фермер
(Время: 1 сек. Память: 16 Мб Сложность: 46%)
Фермер решил на своем квадратном участке земли вспахать пашню квадратной формы максимальной площади, т.к. он посчитал, что именно квадратная форма пашни наиболее удобна для обработки. Но на его участке присутствуют деревья и хозяйственные постройки, которые он никуда не хочет переносить, а так же иные места, не пригодные для пашни. Для удобства он составил квадратную карту местности NxN в форме матрицы и пометил нулями непригодные для пашни зоны, в остальные зоны он поставил единицу.

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

Входные данные

В первой строке входного файла INPUT.TXT записано единственное натуральное число N (1 ≤ N ≤ 1000) – длина стороны квадратного участка фермы. Далее, следует N строк, в каждой из которых находится последовательность (без пробелов) нулей и единиц, описывающих ферму.

Выходные данные

В выходной файл OUTPUT.TXT необходимо вывести максимально возможную площадь пашни.

7
1101101
1111110
1011100
0011100
1000010
1100111
1001110 9

Собственно задачка вроде более менее известная. Может кто-нибудь кинуть какие-нибудь темы по этой задачке или решение, если есть. Если кто-то сможет написать за деньги, то отпишитесь, договоримся

@Amandosov · 29.11.2014, 11:40

Только не уверен пройдет ли он тест на время
так с руки набросал))

C++

// Example program
#include <iostream>
#include <string>
using namespace std;
 
int a[1000][1000],n;
bool prov(int x,int y,int k)
{
for(int i=x;i<=x+k;i++)
for(int j=y;j<=y+k;j++)
if(a[i][j]==0) return false;
return true;    
}
 
int main()
{
char buf;
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{cin>>buf; if(buf=='1') a[i][j]=1; else a[i][j]=0;}
 
for(int k=n-1;k>=0;k--)
for(int i=0;i<n-k;i++)
for(int j=0;j<n-k;j++)
if(prov(i,j,k)) {cout<<(k+1)*(k+1);return 0;}
    
    return 0;
  
}

@Jacky09 · 29.11.2014, 11:44 **[ТС]**

Ох тыж, спасибо большое

@Jacky09 0 / 0 / 0 Регистрация: 15.09.2013 Сообщений: 48
		1
	Задача "Фермер" 29.11.2014, 11:16. Показов 5063. Ответов 2 Метки нет (Все метки) Фермер (Время: 1 сек. Память: 16 Мб Сложность: 46%) Фермер решил на своем квадратном участке земли вспахать пашню квадратной формы максимальной площади, т.к. он посчитал, что именно квадратная форма пашни наиболее удобна для обработки. Но на его участке присутствуют деревья и хозяйственные постройки, которые он никуда не хочет переносить, а так же иные места, не пригодные для пашни. Для удобства он составил квадратную карту местности NxN в форме матрицы и пометил нулями непригодные для пашни зоны, в остальные зоны он поставил единицу. Необходимо помочь фермеру определить максимальную площадь пашни. Входные данные В первой строке входного файла INPUT.TXT записано единственное натуральное число N (1 ≤ N ≤ 1000) – длина стороны квадратного участка фермы. Далее, следует N строк, в каждой из которых находится последовательность (без пробелов) нулей и единиц, описывающих ферму. Выходные данные В выходной файл OUTPUT.TXT необходимо вывести максимально возможную площадь пашни. 7 1101101 1111110 1011100 0011100 1000010 1100111 1001110 9 Собственно задачка вроде более менее известная. Может кто-нибудь кинуть какие-нибудь темы по этой задачке или решение, если есть. Если кто-то сможет написать за деньги, то отпишитесь, договоримся 0

@Jacky09 0 / 0 / 0 Регистрация: 15.09.2013 Сообщений: 48
	29.11.2014, 11:44 [ТС]	3
	Ох тыж, спасибо большое 0

Опции темы

Задача "Фермер"

Решение