|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg I. Khovayko 2:5020/400 03 Feb 2003 18:44:01
To : Ivan Merzlyakov
Subject : Re: Hахождение кратчайшего пути.
--------------------------------------------------------------------------------
Ivan Merzlyakov wrote:
>
> Привет All!
>
> Может это здесь и было, но вот понадобилось.
>
> Есть матрица размерностью (m;m) где m>=5.
> Матрицу заполняем случайным образом цифрами от 0 до 9 кроме 1.
> Задаем стартовую точку и финишную точку, и надо цифрой 1 отрисовать
> минимальный путь от старта к финишу. Если такого нету, т.е на пути нету
> свободного прохода, то ни чего не делаем.
Hе "ни чего", а "ничего". Пишется слитно...
Hа счет топика: задача недоопределена.
Hепонятно:
1. Разрешен ли шаг по диагонали.
2. По каким цифрам можно ходить, а по каким - нельзя.
или по всем ходить можно? Тогда свободный проход есть всегда.
Рассматривая условие с точки зрения банальной эрудиции
предполагаю, что имелось ввиду следующее:
1. Шаг по диагонали запрещен.
2. Ходить можно только по нулям.
Я угадал?
Если да - используй волновой алгоритм, который я
описал в постинге от 6 января.
Делаешь так:
1. Пускаешь волну от источника, причем каждый элемент волны есть
отрицательное число, которое есть сылка на координату
элемента-предшественника. То есть, например, если стартуем из точки
X, Y, то все прилегающие нулевые точки заполняешь числом -(Y * max_Y + X);
То есть все эти точки указывают на X,Y.
2. Когда волной дошел до цели - по этим обратным ссылкам раскручиваешь
кратчайший путь, заменяя пройденый элемент на "1".
3. Удалаешь из матрицы мусор - заменяешь все оставшиеся отрицательные
числа на нули.
--
#include <best/regards.hpp>
Oleg I. KHOVAYKO
(301)435-5885 || WEB: http://olegh.spedia.net
--- ifmail v.2.15dev5
* Origin: National Center for Biotechnology Information (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Hахождение кратчайшего пути. 