Цивілізація
Limits: 2 sec., 256 MiB
Уявіть собі острів, на якому живуть древні племена. Спочатку острів був дуже рідко заселений, але з плином часу людська цивілізація заволоділа ним.
Формально будемо розглядати острів, як прямокутник зі сторонами \(n\) та \(m\). Також для простоти будемо вважати, що кожен квадрат \(1 \times 1\) цього прямокутника в деякий момент часу або повністю заселений, або повністю безлюдний. Відомо, що якщо незаселений квадрат межує із заселеним, то через рік він сам стане заселений. Два квадрати межують один з одним, якщо вони мають спільну сторону.
Вам відома початкова ситуація на острові. Необхідно знайти кількість заселених квадратів через \(k\) років.
Input
У першому рядку містяться три цілих числа \(n\), \(m\) та \(k\) — сторони прямокутника та кількість років.
Кожен із наступних \(n\) рядків містить \(m\) цілих чисел. \(j\)-ий елемент \(i\)-го рядка рівний 1, якщо відповідний квадрат є заселеним, або рівний 0 в протилежному разі.
Output
У єдиному рядку виведіть ціле число — кількість заселених квадратів через \(k\) років.
Constraints
\(1 \le n, m \le 100\),
\(0 \le k \le 10^6\).
Samples
Input (stdin) | Output (stdout) |
---|---|
3 4 1 0 1 0 0 1 0 0 0 0 0 0 1 | 9 |
Notes
Розмір деяких вхідних файлів є більшим за 1 МБ, тому зверніть увагу на функції, які ви використовуєте для зчитування даних. Переконайтесь у тому, що вони є достатньо швидкими.
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|