Моделирование волнового алгоритма на С++
Здравствуйте уважаемые форумчане, без ващей помощи мне не справиться с этой задачей:
В файлах заданы карты двумерных лабиринтов. В программе выбирается карта. Нужна пошаговая демонстрация формирования фронта волны для поиска пути (кратчайшего) между двумя клетками.
Двигаться можно только на соседнюю клетку (по вертикали или по горизонтали). Удобнее формировать путь с конца – тогда можно двигаться от начала в любую сторону уменьшения номера шага.
На первом шаге в список заносятся координаты клеток, смежных с клеткой конца пути, в них помещается «1». На втором – создается список еще не рассмотренных клеток, в которые можно попасть из клеток, помеченных «1», в них заносится «2». И т.д., пока не будет достигнута клетка начала. При просмотре любого списка клетка, для которой помечены соседи, удаляется из списка. Удобно использовать динамическую структуру типа «очередь». Клетки, занятые препятствиями можно пометить «-1».
Для динамической демонстрации распространения фронта волны можно использовать вывод вспомогательной матрицы с числами и матрицы, где препятствия и фронт помечаются квадратиками разного цвета. Перерисовку фронта можно производить в момент перехода на очередной шаг.
Здравствуйте уважаемые форумчане, без ващей помощи мне не справиться с этой задачей:
В файлах заданы карты двумерных лабиринтов. В программе выбирается карта. Нужна пошаговая демонстрация формирования фронта волны для поиска пути (кратчайшего) между двумя клетками.
Двигаться можно только на соседнюю клетку (по вертикали или по горизонтали). Удобнее формировать путь с конца – тогда можно двигаться от начала в любую сторону уменьшения номера шага.
На первом шаге в список заносятся координаты клеток, смежных с клеткой конца пути, в них помещается «1». На втором – создается список еще не рассмотренных клеток, в которые можно попасть из клеток, помеченных «1», в них заносится «2». И т.д., пока не будет достигнута клетка начала. При просмотре любого списка клетка, для которой помечены соседи, удаляется из списка. Удобно использовать динамическую структуру типа «очередь». Клетки, занятые препятствиями можно пометить «-1».
Для динамической демонстрации распространения фронта волны можно использовать вывод вспомогательной матрицы с числами и матрицы, где препятствия и фронт помечаются квадратиками разного цвета. Перерисовку фронта можно производить в момент перехода на очередной шаг.