Архив форумов ЦИТФорума

[fishca]

Помогите с решением задачи, пожалуйста!
Надо найти кратчайший путь из одной точки в другую с обходом прпятствий на пути.

[JekLove]

Рассмотрим случай, когда имеется лабиринт в виде матрицы. Алгоритм следующий. Заполняем все "дорожки" в лабиринте нулями. В начальную клетку записываем единицу. В смежные клетки,
которые являются "свободным пространством",
т.е., по которым можно ходить, пишем двойки. И так далее. Для каждой из клеток, обработанных на предыдущем шаге, повторяем процедуру: в каждую из смежных клеток, в которых стоит ноль, т.е., которые еще не обработаны, записываем номер текущего шага. Ну и на каждом шаге проверяем, является ли данная клетка конечной. Если эта клетка найдется, т.е., к ней есть путь, обрываем цикл и делаем обратную процедуру:
Ищем смежную клетку с номером, меньше того, что стоит в конечной, на единицу. Переходим туда и опять ищем смежную с меньшим на единицу номером. Запоминаем координаты каждой. И таким образом мы всегда дойдем до самой первой, т.е. той, в которой стоит единица. Найденый путь будет кратчайшим. Если путь вообще не существует, на n-ом шаге прямой процедуры не найдется необработынных смежных клеток. Такие дела.

[JekLove]

Рассмотрим случай, когда имеется лабиринт в виде матрицы. Алгоритм следующий. Заполняем все "дорожки" в лабиринте нулями. В начальную клетку записываем единицу. В смежные клетки,
которые являются "свободным пространством",
т.е., по которым можно ходить, пишем двойки. И так далее. Для каждой из клеток, обработанных на предыдущем шаге, повторяем процедуру: в каждую из смежных клеток, в которых стоит ноль, т.е., которые еще не обработаны, записываем номер текущего шага. Ну и на каждом шаге проверяем, является ли данная клетка конечной. Если эта клетка найдется, т.е., к ней есть путь, обрываем цикл и делаем обратную процедуру:
Ищем смежную клетку с номером, меньше того, что стоит в конечной, на единицу. Переходим туда и опять ищем смежную с меньшим на единицу номером. Запоминаем координаты каждой. И таким образом мы всегда дойдем до самой первой, т.е. той, в которой стоит единица. Найденый путь будет кратчайшим. Если путь вообще не существует, на n-ом шаге прямой процедуры не найдется необработынных смежных клеток. Такие дела.