Re: Лабиринты

From

Dmitry Azovtsev ()

To

Andrew Evdokimov

Date

2002-11-21T09:42:20Z

Area

RU.ALGORITHMS

From: "Dmitry Azovtsev" <nospam@azovtsev.com>

Hello, Andrew!

On Fri, 15 Nov 2002 20:09:06 +0300 you wrote:

 AE> Такой вот вопрос - каким образом лучше всего представлять 3-мерные
 AE> лабиринты, имеющие толщину стен?

смотря для чего представлять. Если для поиска выхода - то как граф.
Трехмерность при этом не имеет значения, только наличие прохода
из комнаты в комнату.

 AE> Какие существуют алгоритмы поиска выхода из такого лабиринта?

Стандартные алгоритмы на графах. Волновой, например.

 AE> Интересуют варианты поиска выхода от входа и из произвольной точки
 AE> внутри лабиринта. Интересуют (и это важно) лабиринты с неединственным
 AE> входом и неединственным выходом (здесь тонкость, что входы, отличные от
 AE> того, на котором стоим, не являются валидными выходами).

Все выходы помечаешь как таковые. Входы не помечаешь ;-) Или вводишь
специальную
вершину "наружа" и из выходов прокладываешь туда ребро.

Best regards,
Dmitry

--- ifmail v.2.15dev5
 * Origin: AT&T Broadband (2:5020/400)