Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Castle

Задача  Castle.

Стародавній замок має прямокутну форму. Замок містить щонайменше дві кімнати. Підлогу замка можна умовно поділити на N клітин. Кожна така клітинка містить «0» або «1», які задають порожні ділянки та стіни замку відповідно. Напишіть програму, яка б знаходила площу найбільшої кімнати, яку можна утворити шляхом видалення стіни або її частини, тобто, замінивши лише одну «1» на «0». Видаляти зовнішні стіни заборонено.

Технічні умови. Програма  Castle  читає з пристрою стандартного введення «план замку». Перший рядок містить ціле число M, другий – ціле число  N – кількість рядків та кількість стовпчиків (3 ≤ M ≤ 1000, 3 ≤ N ≤ 1000). M наступних рядків містить по N нулів або одиниць, що йдуть поспіль (без пробілів). Перший та останній рядок, а також перший та останній стовпчик формують зовнішні стіни замку і складаються лише з одиниць. Програма виводить на пристрій   площу найбільшої кімнати, яка утвориться в разі видалення внутрішньої стіни.

Приклади:

Введення

 Виведення

6
8
11111111
10011001
10011001
11111001
10101001
11111111

10

 

 

9
12
111111111111
101001000001
111001011111
100101000001
100011111101
100001000101
111111010101
100000010001
111111111111

 

38

 



© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"