Problems
Гном и монети
Гном и монети
В прямоугольной матрице размером \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}, \textbf{M} - размер матрицы (\textbf{1<=N,M<=50}) и \textbf{K} (\textbf{1<=K<=100}). Следующие \textbf{N} строк по \textbf{M} чисел в каждой описывают план лабиринта.
\textbf{Выходные данные:} Единственное число - максимальное количество собранных монет или \textbf{-1} , если гном не сможет выполнить задание.
Input example #1
3 4 7 0 0 1 2 1 2 0 0 2 1 2 0
Output example #1
2