Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
task1

Задача  Task1.    В компьютерной игре "Страшная месть 2" главного героя – бесстрашного рыцаря – схватили злые и коварные колдуны и спрятали в темном подземелье. Но, к счастью, у славного рыцаря нашлась карта подземелья и несколько ящиков динамита. Каждый ящик динамита может разрушить одну стену. Какое наименьшее количество ящиков динамита должен израсходовать герой, чтобы выбраться из подземелья? Карта лабиринта – лист бумаги в клетку из строк и столбцов. Клетка может быть свободной либо занятой стеной. Герой может перемещаться по свободным клеткам по горизонтали и вертикали. Ящик динамита разрушает стену в одной клетке.  Чтобы выбраться из подземелья, герою достаточно достигнуть границы карты. 
Технические условия 

 Вы вводите с клавиатуры два числа 2<M<100) и N (2<N<100) – количество строк и столбцов в лабиринте, далее в строках по   чисел в каждой вы вводите карту лабиринта:  0 – свободная клетка, 1 – стена, 2 – начальное положение героя. Вы выводите на экран искомое количество ящиков динамита.
Пример 
Ввод:
6 7

1 0 1 0 1
0 2 1 
1 0 1 0 1 0 1
1 0 0 1

Вывод:
2
           В данном примере герою необходимо разрушить две стены, чтобы выбраться из подземелья. 
 


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"