|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Andrianov 2:5020/1507.400 20 Mar 2002 20:07:30
To : Evgeniy Jirnov
Subject : Re: Поможите pls...
--------------------------------------------------------------------------------
Однажды 14-Mar-02 в 01:18 Evgeniy Jirnov (2:5030/1230.13)
написал All по поводу
-=- Поможите pls... -=-
EJ> Мир твоему дому, All.
EJ> Сабж. Имеется матрица(лабиринт) 50x50. 1 - стена, 0 - свободно. Hачальные
EJ> координаты практически от балды(с помощью генератора псевдослуч. чисел).
EJ> Hайти путь из начальной точки в любую точку на границе массива.
EJ> Оптимальность пути некритична, главное чтоб он был. Если пути нет, тогда
EJ> надо это как-то подсчитать. Ежели кто знает как решать подскажите
EJ> алгоритм. Исходники на C, Pas приветствуются. Спасибо за внимание.
Волна: из точки пускаешь волну, т.е. во все смежные с целевой свободные точки
записываешь "2", в смежные с "двойками" - "3" и т.д. до достижения границы.
Оттуда идешь обратно, за каждый шаг "отнимая" по 1.
Если все возможные точки заполнены, а границы не достиг, значит, пути нет.
Kстати, найденный путь будет оптимальным. Hо IMHO не существует алгоритма,
который бы гарантировал непроходимость и при этом более быстрого, чем нахождение
оптимального пути.
До свидания, в 19:01 MSK
Sergey
---
* Origin: Sergiev Posad (2:5020/1507.400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
