Универсальный путевыводитель из лабиринта.

[nikvic]

""Хотел бы в единое слово

Нетрудно придумать порядок, когда это будет неверным.

[TOTAL]

Sonic86 в сообщении #755236 писал(а):

Если я задачу понял неверно, просьба сформулировать ее по-человечески.

Человеческую формулировку задачи можно начать с объяснения того, что такое "выход из комнаты". Ну, вышел я из комнаты, а дальше что, провалился в открытый космос?

[Sonic86]

TOTAL в сообщении #755251 писал(а):

Человеческую формулировку задачи можно начать с объяснения того, что такое "выход из комнаты". Ну, вышел я из комнаты, а дальше что, провалился в открытый космос?

Ну если угодно. Т.е. я дошел до выхода и все, дальше в нем остаюсь навсегда: $U(E)=D(E)=L(E)=R(E)=E$, а для остальных точек - как написано.

Кстати, вот такую тему вспомнил (там есть описание путеводителя для одномерной решетки).

[TOTAL]

Sonic86 в сообщении #755255 писал(а):

TOTAL в сообщении #755251 писал(а):

Человеческую формулировку задачи можно начать с объяснения того, что такое "выход из комнаты". Ну, вышел я из комнаты, а дальше что, провалился в открытый космос?

Ну если угодно. Т.е. я дошел до выхода и все, дальше в нем остаюсь навсегда: $U(E)=D(E)=L(E)=R(E)=E$, а для остальных точек - как написано.

Тогда нет задачи, ведь у каждой комнаты есть выход, я выхожу через него, конец.

[g______d]

Я предполагал, что алгоритм автоматически прерывается, как только мы дошли до выхода.

Предположим, что лабиринт фиксирован и известен. Пронумеруем его комнаты. Из любой комнаты возможен выход, в том числе из первой. Применим алгоритм выхода из первой комнаты. После этого применим алгоритм выхода из комнаты, получающейся из второй комнаты под действием алгоритма выхода из первой комнаты. Это гарантирует нам выход в случае, если мы изначально были в первой или второй комнате. После этого применим алгоритм выхода из комнаты, получающейся из третьей комнаты под действием всего, что было до этого. И так далее. Количество итераций будет в итоге не больше количества комнат.

Если лабиринт заранее неизвестен, то можно перечислить все возможные лабиринты и к каждому применить предыдущий абзац.

[Dave]

nikvic, а Вы можете чётко сформулировать задачу и ответить на следующие вопросы?

1) Лабиринт конечен или бесконечен?
2) Известен ли он заранее?
3) Что означает "выйти из лабиринта"? Выйти в какую-то определённую дверь? Должен ли список команд гарантировать, что мы после этого не войдём обратно в эту же дверь или считается, что выполнение команд после такого "выхода" обрывается?

[Sonic86]

g______d в сообщении #755270 писал(а):

Предположим, что лабиринт фиксирован и известен. Пронумеруем его комнаты. Из любой комнаты возможен выход, в том числе из первой. Применим алгоритм выхода из первой комнаты. После этого применим алгоритм выхода из комнаты, получающейся из второй комнаты под действием алгоритма выхода из первой комнаты. Это гарантирует нам выход в случае, если мы изначально были в первой или второй комнате. После этого применим алгоритм выхода из комнаты, получающейся из третьей комнаты под действием всего, что было до этого. И так далее. Количество итераций будет в итоге не больше количества комнат.

Если лабиринт заранее неизвестен, то можно перечислить все возможные лабиринты и к каждому применить предыдущий абзац.

О! Я понял, благодарю

[nikvic]

Dave в сообщении #755278 писал(а):

nikvic, а Вы можете чётко сформулировать задачу и ответить на следующие вопросы?

1) Лабиринт конечен или бесконечен?
2) Известен ли он заранее?
3) Что означает "выйти из лабиринта"? Выйти в какую-то определённую дверь? Должен ли список команд гарантировать, что мы после этого не войдём обратно в эту же дверь или считается, что выполнение команд после такого "выхода" обрывается?

1/ По умолчанию, "лабиринт" - конечный лабиринт. Исключений не знаю.
2/ Известен. Например, состоит из всех лабиринтиков, с числом комнат не более 666 в каждом
3/ Оказаться в спецкомнате, где накрыта "поляна"

[Deggial]

nikvic в сообщении #755294 писал(а):

1/ По умолчанию, "лабиринт" - конечный лабиринт. Исключений не знаю.
2/ Известен. Например, состоит из всех лабиринтиков, с числом комнат не более 666 в каждом
3/ Оказаться в спецкомнате, где накрыта "поляна"

nikvic, замечание за малосодержательное сообщение.

[nikvic]

В условии не предполагается, что граф лабиринта связен, а вершин со свойством "выход" может быть много.

[lena7]

nikvic
Может вы, наконец, сформулируйте чётко условие задачи и что считается её решением?

[nikvic]

Её решение весьма кратко и точно изложил g______d - 16, 2013 16:14:10.
Полагаю, по нему можно придумать много точных редакций условия.

[Deggial]

nikvic в сообщении #755397 писал(а):

В условии не предполагается, что граф лабиринта связен, а вершин со свойством "выход" может быть много.

nikvic в сообщении #755443 писал(а):

Полагаю, по нему можно придумать много точных редакций условия.

nikvic, ещё одно замечание за кривую формулировку задачи. Вы же понимаете, что если граф лабиринта несвязен, то в общем случае решения нет.
Впредь убедительная просьба формулировать задачи в олимпиадном разделе точно (в следующий раз буду тему в Карантин уносить).

[nikvic]

Deggial в сообщении #755802 писал(а):

Вы же понимаете, что если граф лабиринта несвязен, то в общем случае решения нет.

Вы неправы: нигде не сказано о единственности вершины со свойством "выход". Подразумевается понятие выйти из лабиринта - факт.

[cepesh]

Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Олимпиадные задачи (CS)»
Причина переноса: не указана.