eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Гном і монети

Гном і монети

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

У прямокутній матриці розміром N x M клітин зображено план лабіринту. Кожна клітина описана одним цілим числом:

0 – вільна клітина, яку можна пройти;

1 – перешкода, непрохідна клітина;

2 – вільна клітина, в якій знаходиться одна золота монета.

Вільна клітина з координатами (1,1) – вхід в лабіринт, вільна клітина (N,M) – вихід. Гному, який починає рухатись з стартової клітини необхідно потрапити в кінцеву клітину за обмежений час, що складає K хв. Гном може рухатись по сусідніх вільних клітинах, зробивши крок через їх спільну сторону, причому на прохід будь-якої однієї клітини гном витрачає 1 хв. Відомо, що кількість золотих монет в лабіринті, як і час, теж обмежена, наприклад числом 10.

Але чому не об’єднати приємне з корисним, тобто всі монети з клітин, де побував гном він може забрати собі. Яку найбільшу кількість монет може зібрати гном, при описаних вище умовах?

Вхідні дані: В першому рядку три числа: N, M – розмір матриці (1<=N,M<=50) та K (1<=K<=100). Наступні N рядків по M чисел в кожному описують план лабіринту.

Вихідні дані: Одне число – максимальна кількість зібраних монет або -1, якщо гном не може виконати завдання.

Приклад

Вхідні дані #1
3 4 7
0 0 1 2
1 2 0 0
2 1 2 0
Вихідні дані #1
2
Джерело Житомирська ХХVIII обласна олімпіада з інформатики