Задача Task1. В компьютерной игре "Страшная месть 2" главного героя – бесстрашного рыцаря – схватили злые и коварные колдуны и спрятали в темном подземелье. Но, к счастью, у славного рыцаря нашлась карта подземелья и несколько ящиков динамита. Каждый ящик динамита может разрушить одну стену. Какое наименьшее количество ящиков динамита должен израсходовать герой, чтобы выбраться из подземелья? Карта лабиринта – лист бумаги в клетку из M строк и N столбцов. Клетка может быть свободной либо занятой стеной. Герой может перемещаться по свободным клеткам по горизонтали и вертикали. Ящик динамита разрушает стену в одной клетке. Чтобы выбраться из подземелья, герою достаточно достигнуть границы карты.
Технические условия
Вы вводите с клавиатуры два числа M ( 2<M<100) и N (2<N<100) – количество строк и столбцов в лабиринте, далее в M строках по N чисел в каждой вы вводите карту лабиринта: 0 – свободная клетка, 1 – стена, 2 – начальное положение героя. Вы выводите на экран искомое количество ящиков динамита.
Пример
Ввод:
6 7
1 1 1 1 1 1 1
1 0 1 1 1 0 1
1 1 0 2 1 1 1
1 0 1 0 1 0 1
1 0 0 1 1 0 1
1 1 1 1 1 1 1
Вывод:
2
В данном примере герою необходимо разрушить две стены, чтобы выбраться из подземелья.