Задача Castle.
Стародавній замок має прямокутну форму. Замок містить щонайменше дві кімнати. Підлогу замка можна умовно поділити на M x 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
|
|
|