Музикант заразний
Limits: 2 sec., 256 MiB
Подейкують, що навіть щеплення вже роблять!
Уявіть собі матрицю \(n \times n\), кожна клітинка якої має свій ступінь захисту від Музиканта. Спочатку клітинка \((1, 1)\) є зараженою Музикантом. Якщо в поточний момент заражена клітинка має додатний ступінь захисту \(k\), то через хвилину він буде рівним \(k-1\). Якщо ступінь захисту клітинки став рівним 0, то вона заражає синдромом клоунізму всі сусідні раніше не заражені клітинки, а сама помирає. Клітинки вважаються сусідніми, якщо в них є спільна сторона.
Вам необхідно визначити кількість мертвих клітинок через \(m\) хвилин.
Input
Перший рядок містить два цілі числа \(n\) та \(m\) — розмір матриці та кількість хвилин.
Наступні \(n\) рядків містять по \(n\) цілих чисел \(a_{i j}\) — ступені захисту відповідних клітинок.
Output
У єдиному рядку виведіть ціле число — кількість убитих Музикантом бідолашних клітинок.
Constraints
\(1 \le n \le 100\),
\(1 \le m \le 10^9\),
\(1 \le a_{i j} \le 10^9\).
Samples
Input (stdin) | Output (stdout) |
---|---|
2 2 1 1 1 1 | 3 |
Input (stdin) | Output (stdout) |
---|---|
5 37 9 6 6 7 1 9 9 3 5 3 10 1 9 7 9 3 1 6 9 9 5 6 9 1 9 | 19 |
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 |
---|