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


Годинник
 
Walls

Задача WALLS. 

В комп'ютерній грі "Страшна помста 2" головного героя -безстрашного лицаря - схопили злі та підступні чаклуни і сховали в темному підземеллі. Але, на щастя, у славного лицаря знайшлась карта підземелля та кілька ящиків динаміту. Кожний ящик динаміту може зруйнувати одну стіну. Яку наименшу кількість ящиків динаміту повинен витратити герой, щоб вибратися з підземелля?
Карта лабиринту - це аркуш паперу в клітинку з M рядків та N стовпців. Клітка може бути вільною або зайнятою стіною. 
Герой може рухатися вільними клітинками по горизонталі або вертикалі. Ящик динаміту руйнує стіну в одній клітинці. 
Щоб вибратися з підземелля, герою достатньо досягнути границі карти.
Ви повинні написати програму WALLS, яка читає вхідні дані з клавіатури та виводить відповідь в файл на екран.

Формат введення>
M N
p[1,1] p[1,2] ј p[1,N]
p[2,1] p[2,2] ј p[2,N]
ј
p[M,1] p[M,2] ј p[M,N]


Формат виведення
X

Тут M та N - число рядків та стовпців на карті підземелля. p[i,j]=0, якщо в цьому місці підземлля відсутня стіна, p[i,j]=1 - якщо стіна є, p[i,j]=2 позначає початкове положення героя, X - мінімальна кількість ящиків динаміту, яку потрібно витратити, щоб вибратися із підземелля.

Обмеження:
2<M<100;
2<N<100.

Приклад:
Введення:
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

В цьому прикладі герою потрібно зруйнувати дві стіни, щоб вибратися з підземелля.


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