Версия для печати темы

Автор: Andrej_87 17.03.2007 1:22

Здравствуйте! помогите пожалуйста решить задачу.Не могу понять как её нужно реализовать?

Матрица размера N*M определяет некоторый лабиринт. B матрице элемент 1 обозначает стену, а 0 определяет свободное место. В первой строке матрицы определяются входы x(i), а в последней выходы y(i), i=1,..,k, которые должны быть нулевыми элементами.

Необходимо определить, можно ли

а) провести k человек от входа x(i) до выхода y(i) соответственно, i=1,..,k, таким образом, чтобы каждое свободное место посещалось не более одного раза.

б) то же, но человека можно выводить чеpез любой из выходов. Примечание: Движение в лабиринте осуществляется только по вертикали или горизонтали.

Автор: Lapp 17.03.2007 3:14

Проясни, пожалуйста, один момент.
Клетка должна посещаться не более одного раза каждым жуком или всеми? То есть если первый тма был - второй может туда пойти?

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

Так что условие получается не совсем корректным..

Автор: Andrej_87 18.03.2007 0:16

В условии было намисано только это. Я думаю всё таки Клетка должна посещаться более одного раза каждым жуком.

Автор: Andrej_87 20.03.2007 0:56

Я нашёл алгоритм и не могу описать его на языке. Помогите пожалуйста ЛЮДИ!
Вот алгоритм:
Основная стратегия человека, вошедшего в самый левый вход, состоит в прохождении лабиринта, используя наиболее левые свободные места лабиринта, т.е. он должен двигаться, держась правой рукой за "стенку" лабиринта. Этот процесс можно формализовать следующим образом. Находясь в очередной позиции лабиринта, он должен помнить, с какой стороны он пришел сюда (слева, справа, сверху, снизу), и, руководствуясь этой информацией, вобрать следующее наиболее предпочтительное направление в новую позицию (куда он может пойти и где еще не был). При этом удобно использовать стек, в верхушке которого находятся координаты текущей позиции и направление, по которому в нее пришли. При этом все посещенные клетки метятся. Легко заметить, что если в позицию попали сверху, то наилучшим направлением будет налево, затем вниз, направо, и наконец назад (вверх). Аналогично можно определить наилучшие направления для других случаев.
Эта стратегия повторяется каждым из людей, при этом позиции, помеченные предыдущими людьми, считаются запрещенными для следующих.