Моделирование волнового алгоритма на С++
Здравствуйте уважаемые форумчане, без ващей помощи мне не справиться с этой задачей:
В файлах заданы карты двумерных лабиринтов. В программе выбирается карта. Нужна пошаговая демонстрация формирования фронта волны для поиска пути (кратчайшего) между двумя клетками. Двигаться можно только на соседнюю клетку (по вертикали или по горизонтали). Удобнее формировать путь с конца – тогда можно двигаться от начала в любую сторону уменьшения номера шага. На первом шаге в список заносятся координаты клеток, смежных с клеткой конца пути, в них помещается «1». На втором – создается список еще не рассмотренных клеток, в которые можно попасть из клеток, помеченных «1», в них заносится «2». И т.д., пока не будет достигнута клетка начала. При просмотре любого списка клетка, для которой помечены соседи, удаляется из списка. Удобно использовать динамическую структуру типа «очередь». Клетки, занятые препятствиями можно пометить «-1». Для динамической демонстрации распространения фронта волны можно использовать вывод вспомогательной матрицы с числами и матрицы, где препятствия и фронт помечаются квадратиками разного цвета. Перерисовку фронта можно производить в момент перехода на очередной шаг. |
Часовой пояс GMT +4, время: 13:13. |
Powered by vBulletin® Version 4.5.3
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.