Представьте, что вы находитесь в лаборатории. Вы исследуете умение крыс ориентироваться в незнакомых лабиринтах. У вас есть конструктор для создания односвязных лабиринтов. Односвязный лабиринт - означает, что лабиринт не содержит замкнутых маршрутов, т.е. таких, которые образуют замкнутую петлю. Замкнутый маршрут возникает в том случае, если существует ограниченный стенками «остров», который не соединяется с другими стенками лабиринта.
Чтобы анализировать поведение крысы в лабиринте, вам необходимо заранее знать кратчайший маршрут от точки входа, до сыра, расположенного в этом лабиринте. Так как подсчет длины кратчайшего пути - достаточно рутинная работа, вы решили запрограммировать робо-мышь, которая ищет длинну кратчайшего пути автоматически.
Вашей конечной задачей является подсчет минимального количества шагов, за которые крыса может добраться от точки входа до сыра.
Файл input.txt, который содержит в себе набор символов с шириной W и высотой H, где:
- ' '(пробел) - свободный путь;
- '#'(решетка) - стена;
- '1'(единица) - точка входа;
- '0'(ноль) - сыр или конечная точка (точка выхода).
Минимальное количество шагов, за которое можно добраться от 1 до 0 не пересекая стены.
- Содержимое файла
input.txt:
#######
#1# #
# # # #
# # #
### ###
# 0#
#######
Answer = 8
- Содержимое файла
input.txt:
###########
#1 # #
### # # ###
# # # #
# ### # # #
# # # #
# # # # # #
# # # # # #
# ### # # #
# # # #0#
###########
Answer = 20