Лабиринт
Автор задачи: Андрей Гайдель
Первоисточник: -
URL первоисточника: -
Задачу добавил: LGR
Успешно сдано решений: 22
3008 год. Земляне наконец-то решили сделать раскопки под Большим Сфинксом в Египте. Это, конечно, неспроста: они прозвонили всю территорию вокруг него гиперрентгеновскими лучами и увидели кучу золота, бриллиантов, платины и других интересных вещей. Все пророчества о проклятье сфинкса были отброшены, как несостоятельные. Немедленно нашлась группа исследователей, которая была готова перерыть всю пустыню в поисках предметов древнеегипетского искусства. Перерыли. Нашли вход в сеть длинных корридоров, карта которых также была построена с помощью гиперрентгеновских лучей. Но только они вошли внутрь, как проход обрушился, причём очень сильно. Исследователи решили не сидеть на месте, а добраться до сокровищ, пока их самих выкапывают снаружи. Правда, возух был слегка спёртый, в связи с чем это нужно было сделать как можно быстрее. Ваша задача - по карте лабиринта найти кратчайший путь до сокровищ.Входные данные
Файл input.txt содержит карту лабиринта в виде символьной матрицы. В первой строке содержутся целые числа N и M - (2<=N,M<=1000). Далее в N строках содержутся описания строк матрицы. В каждой строке содержутся M символов, которые следует трактовать следующим образом:
! - текущее местоположение группы исследователей;
= - стена лабиринта;
<пробел> - проход в лабиринте;
+ - место, где спрятаны сокровища.
Выходные данные
Файл output.txt должен содержать единственное число - минимальное количество перемещений (перемещаться можно по коридору вправо, влево, вверх или вниз) за которое исследователи доберуться до сокровищ, или слово NO, если проход к сокровищам закрыт.
Пример
input.txt
5 6
!= =+
=
=
= =
=
output.txt
9