Нахождение кратч. пути межд. точками

Как найти кратчайшее расстояние между двумя точками в 2D массиве? Причем ийти только через ичейки хранящие ноль. Алгоримов не надо, а советы давайте.

алгоритмов не надо, алгоритмов не надо... а как же тогда?
ладно, попробуем:)

попробуй сделать второй массив, и начинай расширятся из одной из этих точек..
во все сосдение, которые нули ставь 1, во все, в которые можно добраться из соседних (клетки, соседние с соседними и равные 0) ставь 2
те, куда дойдешь за три хода, в них ставь 3.
так доползешь и до своей:) второй точки. что в нее напишешшь, то и будет кратчайшее расстояние.. а путь потом можно восстановить:)

Если по диагонали нельзя ходить, то задача разбиваеться на поиск кратчайшего растояния в обычных масивах - рядках и столбиках етой матрицы

Ладно, надеюсь Вы не обидились за "Ненадо алгоритмов", они всегда нужны, только тут проблема: все хорошие проги писаны на С++, а я в нем господин дерево, если сможите объяснить языком VB, или Delphi, буду примного благодарен.

Я тут сам попробовал написать так: нашёл окольный путь, и прописал его в другом масссиве, сколько ходов потребовалось для прохождения до данной точки массива. Потом ещё раз прошёлся, но если получалось, что путь длиннее, его обрывало. И так до бесконечности, пока не поймёт, что путь найден. Подобный способ есть в одной книжке по делфи, но там он 5x5, и какой то принцип свой, вроде массив 2д, а координаты опеределявтся одним аргументом. Ну в общем, в массиве 100x100 на всё это уходит около 2 минут, в реал тайм не катит.

да тут способов море....
можно для этих нужд любой алгоритм поиска переделать, например Дейкстры...

А енти ваши Дейкстры быстрые?

ну как сказать......... не самый медленный.
нужно будет матрицу вашу правда малость преобразовать для этих нужд.

ЗЫ а вообще у вас тут что-то вроде лабиринта..... можно волновым алгоримом пользоваться

Глубокоуважаемый  и высокообразованый rhf, в нашей деревне таких терменов просто не знают. А насчет лабиринтов, но ответ отрицательный: просто пара линий. Буду примного благодарен за любую доку, пример на любой (кроме ассемблера) язык, или просто письмо с оъяснением. Мыло моё (личное) :

b.ivan@nursat.kz

или belyaev.iv@mail.com, но с этим чо-то не так, видимо с кодировкой.

Цитата Иван, 16.09.02, 17:57:33

в нашей деревне таких терменов просто не знают

Аналогия волновой алгоритма - ты бросаешь камень в воду и смотришь, как расходятся волны от него. (Конечно, так можно и "поехать", но не в этом дело!). На N-ом ходу ты ставишь во все соседние клетки с числом (N-1) min(N, число в клетке).
Пример на паскалях-псевдокоде:
Mas[X,Y] = -1 - стена
Mas[StartX, StartY]:=1;
for i:=1 to N do
for j:=1 to N do
 for k:=1 to N do
  for l:=1 to N do
   if Mas[I,J] <> -1 Then
    Mas[I,J]:=минимум из значений в соседних клетках + 1;

Я не гарантирую, что алгоритм самый быстрый, но что работает - точно...

2 tserega, хе......уж точно не быстрый четыре вложенных цикла......
2 Иван, зная название алгоритма не проблема найти его в сети....
зыж примерчик решения на мыло вам скинул, проверьте.

Так я и не говорю, что быстрый. Вопрос был хоть какой-то алгоритм. Мое дело - предложить, другое дело оптимизация.

К rhf. Видимо Вы кинули пример на глючное мыло, ну или чтото с ним случилось по дороге. Прошу кинуть ещё раз на b.ivan@nursat.kz

Цитата rhf, 13.09.02, 20:45:58

да тут способов море....
можно для этих нужд любой алгоритм поиска переделать, например Дейкстры...

Да не переделывать, а это и есть ненаправленный граф , причём упрощеный.

Сообщение отредактировано: TrivialCore - 21.09.02, 21:27

YtНедавно ограммил халяву одному студенту - 25х25
Расчет практически не заметен под TVision
Dscska. на мыло b.ivan@nursat.kz

Блин, достал PuntoSwitcher, как хочет, так и переключает
отправил на адрес belyaev.iv@mail.com, а другой не не доступен.
Если нужен exe, то сообщи здесь.