Ответ

serglif 16.08.2004 14:34

У меня был похожий курсовик лет 5 назад. Алгоритма не найду, не сохранился, но кое-что могу рассказать:

1. Не берусь утверждать за оптимальность подхода, но теория предлагала нам решать такие задачи через матрицы смежности из теории графов. В вашем случае вершины графа это комнаты, а ребра двери меду ними. Матрица смежности это таблица, где в i-ой строке и j-ом столбце стоит 1, если вершины i и j смежны. В вашем случае для вершин 1-2-3-4-5-6-7-8 имеем что-то типа:

. 1 . . 1 . . .
1 . . . . . . .
. . . . . . 1 .
. . . . . . . 1
1 . . . . . . .
. . . . . . 1 .
. . 1 . . 1 . 1
. . . 1 . . 1 .

Вот с такими таблицами обычно работают в данных случаях.

2. Я насколько помню обходился без рекурсии. Строил динамический массив путей, который в цикле продлевал по матрице смежности.

3. Тупик очевидно при таком подходе - когда в строке матрицы нет единиц, кроме как в позиции, равной предыдущему пункту пути.

Вообщем и целом - вам очевидно нужна теория графов. :)

---