Лабиринт Ариадны

[sweex1234]

Попал в лабиринт, состоящий из одинаковых квадратных комнат, каждая из которых может иметь от 1 до 4 выходов в соседние комнаты, путник долго блуждал по нему, пока не нашел клад. Во время поиска он создал описание своего маршрута, обозначил каждый переход из комнаты в комнату буквами: П1 (север), С (восток), П2 (юг), С (запад). Описать алгоритм, определяющий по заданному записи кратчайший путь назад.

[nfb]

Восток и запад одинаково обозначаются?

[sweex1234]

извините, нет.... запад-z

[nfb]

Ну тогда как описать?

Читать маршрут с конца по порядку. Сначала первая (ну то есть последняя) буква.
Условие: если север, идем на юг, если юг, идем на север, если восток, идем на запад, если запад, идем на восток.
Далее читаем вторую букву, то же условие. Третью и т.д. Вуаля, и вот мы в первой комнате (дома).

[evg_m]

Далее читаем вторую букву, то же условие. Третью и т.д

но

путник долго блуждал по нему,

стало быть возможны петли (проход через одну комнату несколько раз). А стоит задание найти КРАТЧАЙШИЙ путь.

[nfb]

блин, вот слово кратчайший я пропустила))

значит так:
читаем путь в с начала, определяем две целочисленные переменные X и Y, равные 0, смотрим первую букву:
если север, х ++, если юг: х--, восток: у++, запад: у--
и так для каждой буквы в записанном пути.
после этого знаем х и у. исходя из того что начало пути 0 0, нетрудно вернуться туда.
если х > 0 идем на юг х раз, иначе если х<0 идем на север х раз, иначе стоим на месте;
если у>0 идем на запад у раз, иначе если у<0 идем на восток у раз, иначе стоим на месте

вроде так.

[evg_m]

если х > 0 идем на юг х раз, иначе если х<0 идем на север х раз,

а если там нет двери в нужном направлении?

каждая из которых может иметь от 1 до 4 выходов в соседние комнаты

иначе стоим на месте

означает пришли в тупик?

[nfb]

тогда я просто пойду спать)))))