Лабиринт, - |
Лабиринт, - |
Andrej_87 |
16.03.2007 21:22
Сообщение
#1
|
Группа: Пользователи Сообщений: 5 Пол: Мужской Репутация: 0 |
Здравствуйте! помогите пожалуйста решить задачу.Не могу понять как её нужно реализовать?
Матрица размера N*M определяет некоторый лабиринт. B матрице элемент 1 обозначает стену, а 0 определяет свободное место. В первой строке матрицы определяются входы x(i), а в последней выходы y(i), i=1,..,k, которые должны быть нулевыми элементами. Необходимо определить, можно ли а) провести k человек от входа x(i) до выхода y(i) соответственно, i=1,..,k, таким образом, чтобы каждое свободное место посещалось не более одного раза. б) то же, но человека можно выводить чеpез любой из выходов. Примечание: Движение в лабиринте осуществляется только по вертикали или горизонтали. |
Lapp |
16.03.2007 23:14
Сообщение
#2
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
провести k человек от входа x(i) до выхода y(i) соответственно, i=1,..,k, таким образом, чтобы каждое свободное место посещалось не более одного раза. Проясни, пожалуйста, один момент. Клетка должна посещаться не более одного раза каждым жуком или всеми? То есть если первый тма был - второй может туда пойти? Ответ, скорее всего, такой: не может. Потому что совсершенно ясно, что один жук всегда может пройти без повторений (повторение - это всегда петля, их можно исключить) своих пройденных клеток. Но тогда второй вопрос становится неразрешимым. Потому что, если входы и выходы занумерованы по порядку (слева направо), то как ни крути, а при прохождении от входа 1 к выходу 2 обязательно придется пересечь путь от входа 2 к выходу 1. Так что условие получается не совсем корректным.. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Andrej_87 |
17.03.2007 20:16
Сообщение
#3
|
Группа: Пользователи Сообщений: 5 Пол: Мужской Репутация: 0 |
В условии было намисано только это. Я думаю всё таки Клетка должна посещаться более одного раза каждым жуком.
|
Andrej_87 |
19.03.2007 20:56
Сообщение
#4
|
Группа: Пользователи Сообщений: 5 Пол: Мужской Репутация: 0 |
Я нашёл алгоритм и не могу описать его на языке. Помогите пожалуйста ЛЮДИ!
Вот алгоритм: Основная стратегия человека, вошедшего в самый левый вход, состоит в прохождении лабиринта, используя наиболее левые свободные места лабиринта, т.е. он должен двигаться, держась правой рукой за "стенку" лабиринта. Этот процесс можно формализовать следующим образом. Находясь в очередной позиции лабиринта, он должен помнить, с какой стороны он пришел сюда (слева, справа, сверху, снизу), и, руководствуясь этой информацией, вобрать следующее наиболее предпочтительное направление в новую позицию (куда он может пойти и где еще не был). При этом удобно использовать стек, в верхушке которого находятся координаты текущей позиции и направление, по которому в нее пришли. При этом все посещенные клетки метятся. Легко заметить, что если в позицию попали сверху, то наилучшим направлением будет налево, затем вниз, направо, и наконец назад (вверх). Аналогично можно определить наилучшие направления для других случаев. Эта стратегия повторяется каждым из людей, при этом позиции, помеченные предыдущими людьми, считаются запрещенными для следующих. |
Текстовая версия | 30.04.2024 12:19 |