Лабиринт

Добро пожаловать в итоговый проект! Собака попала в лабиринт из живых изгородей. В редакторе лежит программа из урока «Условия», которая уверенно проводила собаку по любой извилистой дорожке. Запустите её и понаблюдайте за первой картой.

Собака ходит туда-сюда и никак не доходит до цели. Почему? На извилистой дорожке из каждого места можно было идти дальше только одним способом. А в лабиринте есть развилки. На развилке программа из урока «Условия» всегда идёт прямо, поэтому никогда не сворачивает в боковой проход. Она доходит до конца коридора, разворачивается, идёт до другого конца и так далее, снова и снова. Программа, которая работает на одних данных, может вести себя совсем иначе на других. Поэтому программы проверяют на как можно более разнообразных входных данных.

Для лабиринтов есть простой и знаменитый алгоритм — правило правой руки. Приложите правую руку к стене лабиринта и никогда её не отнимайте. Если всё время идти вдоль стены, вы дойдёте до цели в любом лабиринте, у которого все стены связаны. Лабиринты в этом курсе именно такие.

Для собаки это значит следующее. На каждом проходе цикла:

1. Если есть путь направо, она поворачивает направо и делает шаг.
2. Иначе, если есть путь вперёд, она делает шаг.
3. Иначе она поворачивает налево.

Обратите внимание: в первом пункте собака делает шаг сразу после поворота направо. Если бы не делала, на следующем проходе она снова увидела бы путь направо (тот, откуда только что пришла) и крутилась бы на месте. А в третьем пункте, наоборот, достаточно просто повернуться: на следующем проходе собака решает заново, уже видя другое. В тупике она дважды поворачивает налево и идёт обратно.

Эти решения вам знакомы из урока «Условия»; нужны только другой порядок и другое содержание. Измените программу или соберите её заново.