Kamrad.ru - Программисты, отзовитесь!

Kamrad.ru (https://kamrad.ru/index.php)
- Программы (software) (https://kamrad.ru/forumdisplay.php?forumid=11)
-- Программисты, отзовитесь! (https://kamrad.ru/showthread.php?threadid=30494)

GoldenAndy 18-04-2002 10:51:

Программисты, отзовитесь!

Подскажите мне, юному хацкеру, алгоритм решения следующей задачи:

Соеденить максимально короткой линией две точки на прямоугольном поле с препятствиями.
Другая формулировка - Найти выход из лабиринта, "коридоры" которого имеют разную ширину ..

Пробовал вариант рекурсивного поиска - неоправданно долго... Хотя работает....

Просьба крутым хацкерам ногами не пинать!
ответ мона в мыло...

Moonshade 18-04-2002 11:36:

Обход есть в инете. Поищи. Например, волной, если мне память не изменяет.

GoldenAndy 18-04-2002 13:30:

Волной - это как ?
где искать ?

Thomas Anderson 25-04-2002 19:45:

Волной - это так (на примере листка в клетку):
1. Нарисую прямоугольник, конечную и начальную точки, преграды.
2. Вокруг последней точки ставяться единицы (где можно).
3. В соседних с единицами пустых клетках ставяться двойки.
...
13. В соседних с 12-ю пустых клетках ставяться 13.
...
n. Когда дорисуешся до начала (откуда рисовать линию), соединяешь её с клеткой с меньшей цифрой. Эту соединяешь с клеткой с ещё меньшей цифрой (14->13->12) и так до конца.

Текущее время: 09:42