Лабиринт, - Опции

[Andrej_87]

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

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

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

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

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

[Lapp]

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

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

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

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

[Andrej_87]

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

[Andrej_87]

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