Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Лабиринт

Автор задачи: Андрей Гайдель

Первоисточник: -

URL первоисточника: -

Задачу добавил: LGR

Успешно сдано решений: 22

    3008 год. Земляне наконец-то решили сделать раскопки под Большим Сфинксом в Египте. Это, конечно, неспроста: они прозвонили всю территорию вокруг него гиперрентгеновскими лучами и увидели кучу золота, бриллиантов, платины и других интересных вещей. Все пророчества о проклятье сфинкса были отброшены, как несостоятельные. Немедленно нашлась группа исследователей, которая была готова перерыть всю пустыню в поисках предметов древнеегипетского искусства. Перерыли. Нашли вход в сеть длинных корридоров, карта которых также была построена с помощью гиперрентгеновских лучей. Но только они вошли внутрь, как проход обрушился, причём очень сильно. Исследователи решили не сидеть на месте, а добраться до сокровищ, пока их самих выкапывают снаружи. Правда, возух был слегка спёртый, в связи с чем это нужно было сделать как можно быстрее. Ваша задача - по карте лабиринта найти кратчайший путь до сокровищ.

    Входные данные
    Файл input.txt содержит карту лабиринта в виде символьной матрицы. В первой строке содержутся целые числа N и M - (2<=N,M<=1000). Далее в N строках содержутся описания строк матрицы. В каждой строке содержутся M символов, которые следует трактовать следующим образом:
! - текущее местоположение группы исследователей;
= - стена лабиринта;
<пробел> - проход в лабиринте;
+ - место, где спрятаны сокровища.

    Выходные данные
    Файл output.txt должен содержать единственное число - минимальное количество перемещений (перемещаться можно по коридору вправо, влево, вверх или вниз) за которое исследователи доберуться до сокровищ, или слово NO, если проход к сокровищам закрыт.

    Пример
   
input.txt
5 6  
!= =+
=
=
= =
=

output.txt
9

Сдать задачу

Задать вопрос жюри по этой задаче