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

[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.

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