Линии

← →
Merlin (2001-11-16 11:23) [9]

> нельзя приближаться к объекту удаляясь от него
Запросто! "Назад в будущее" смотрел? :)))

Вот в таком лабиринте
B.... ####. ...#. .#.#. A#...
тебе однозначно придется удаляться от точки "B" некоторое время.

Для поиска кратчайшего пути в любом лабиринте, я бы сделал так:
1. Есть двумерный массив.
2. Исходная точка и конечная точка
3. В массиве преграды как-то помечены
4. В исходную точку ставим воображаемый шарик
5. Каждый воображаемый шарик ставит потомков во все свободные клетки вокруг себя (можно ходить по диаганали или нет, это уж как захочется)
6. Каждый воображаемый шарик имеет порядковый номер. Тот что в исходной точке 0, он поставил вокруг себя 1-е, те вокруг 2-е и т.д.
7. Когда воображаемый шарик ставит вокруг себя потомков, он может заменить какой-то другой воображаемый шарик рядом с собой, если у того, порядковый номер больше, чем у нашего потомка! (если этого не делать, то мы тоже найдем возможный путь, но он не всегда будет кратчайшим)
8. Так в цикле ползем до тех пор, пока какой-то воображаемый шарик не доберется до конечной точки.
9. Получаем кратчайший свободный путь двигаясь от конечной точки по воображаемым шарикам с номером на 1 меньше чем у текущего.

Чтобы стало понятнее, лучше нарисую.
Имеем:

B.... ###.. ...#. .#... A.... #- преграды A- исходная точка B- конечная Для того, чтобы меньше рисовать, допустим, по диагонали ходить можно. Поехали: B.... ###.. ...#. 1#... A1... B.... ###.. 22.#. 1#2.. A12.. B.... ###.. 223#. 1#23. A123. B.... ###4. 223#4 1#234 A1234 B.555 ###45 223#4 1#234 A1234 B6555 ###45 223#4 1#234 A1234
Дошли до конечной. От нее в обратном направлении, топаем по шарикам с меньшим номером на единицу:
Звездочками помечаю:
B**55 ###*5 22*#4 1#*34 A*234
Вот и получили кратчайший путь.
Осталось это реализовать :) Я такое делал еще в школе, но программы не сохранилось... :(

Линии Найти похожие ветки