Задача 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
В цьому прикладі герою потрібно зруйнувати дві стіни, щоб вибратися з підземелля.