Гном и монеты
В прямоугольной матрице размером 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 , если гном не сможет выполнить задание.