Задачі
Гном і монети
Гном і монети
У прямокутній матриці розміром \textbf{N x M} клітин зображено план лабіринту. Кожна клітина описана одним цілим числом:
\textbf{0} -- вільна клітина, яку можна пройти;
\textbf{1} -- перешкода, непрохідна клітина;
\textbf{2} -- вільна клітина, в якій знаходиться одна золота монета.
Вільна клітина з координатами (\textbf{1,1}) -- вхід в лабіринт, вільна клітина (\textbf{N,M}) -- вихід. Гному, який починає рухатись з стартової клітини необхідно потрапити в кінцеву клітину за обмежений час, що складає \textbf{K }хв. Гном може рухатись по сусідніх вільних клітинах, зробивши крок через їх спільну сторону, причому на прохід будь-якої однієї клітини гном витрачає \textbf{1} хв. Відомо, що кількість золотих монет в лабіринті, як і час, теж обмежена, наприклад числом \textbf{10}.
Але чому не об’єднати приємне з корисним, тобто всі монети з клітин, де побував гном він може забрати собі. Яку найбільшу кількість монет може зібрати гном, при описаних вище умовах?
\textbf{Вхідні дані}: В першому рядку три числа: \textbf{N, M} -- розмір матриці (\textbf{1<=N,M<=50}) та \textbf{K} (\textbf{1<=K<=100}). Наступні \textbf{N} рядків по \textbf{M} чисел в кожному описують план лабіринту.
\textbf{Вихідні дані}: Одне число -- максимальна кількість зібраних монет або \textbf{-1}, якщо гном не може виконати завдання.
Вхідні дані #1
3 4 7 0 0 1 2 1 2 0 0 2 1 2 0
Вихідні дані #1
2