Цивілізація
Обмеження: 2 сек., 256 МіБ
Уявіть собі острів, на якому живуть древні племена. Спочатку острів був дуже рідко заселений, але з плином часу людська цивілізація заволоділа ним.
Формально будемо розглядати острів, як прямокутник зі сторонами \(n\) та \(m\). Також для простоти будемо вважати, що кожен квадрат \(1 \times 1\) цього прямокутника в деякий момент часу або повністю заселений, або повністю безлюдний. Відомо, що якщо незаселений квадрат межує із заселеним, то через рік він сам стане заселений. Два квадрати межують один з одним, якщо вони мають спільну сторону.
Вам відома початкова ситуація на острові. Необхідно знайти кількість заселених квадратів через \(k\) років.
Вхідні дані
У першому рядку містяться три цілих числа \(n\), \(m\) та \(k\) — сторони прямокутника та кількість років.
Кожен із наступних \(n\) рядків містить \(m\) цілих чисел. \(j\)-ий елемент \(i\)-го рядка рівний 1, якщо відповідний квадрат є заселеним, або рівний 0 в протилежному разі.
Вихідні дані
У єдиному рядку виведіть ціле число — кількість заселених квадратів через \(k\) років.
Обмеження
\(1 \le n, m \le 100\),
\(0 \le k \le 10^6\).
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
3 4 1 0 1 0 0 1 0 0 0 0 0 0 1 | 9 |
Примітки
Розмір деяких вхідних файлів є більшим за 1 МБ, тому зверніть увагу на функції, які ви використовуєте для зчитування даних. Переконайтесь у тому, що вони є достатньо швидкими.
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|