Решение лабиринта с использованием графа

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

Напишите программу, которая загружает из файла размер лабиринта, а затем сам лабиринт. Для моделирования лабиринта мы используем символ «S», который определяет начальную ячейку, «.» которая указывает свободную ячейку, "#" - стена, а "F" - последняя ячейка. Напишите программу, которая находит путь из начальной ячейки в конечную. Можно подумать, что в лабиринте находится робот, который подчиняется командам, поэтому для следующего лабиринта робот должен получать следующие команды: вверх, вверх, вправо, вправо, вниз, вниз.

лабиринт 1 текстовый файл

5 5
#####
#...#
#.#.#
#S#T#
#####

лабиринт 2 текстовый файл

4 5
#.#.#
#.#.#
#S#T#
#####

Напишите свою программу в целом (максимальный ввод лабиринта может быть не более 200x200).

Помощь будет высоко оценена. Я всего лишь второкурсник, поэтому, если бы вы могли предоставить мне код, я бы понял его, и они снова сделали бы это сами.


c++ graph breadth-first-search depth-first-search maze
person catvsrat    schedule 14.11.2010    source источник
comment
@rwilliams: это не домашнее задание.   -  person Cam    schedule 14.11.2010
comment
Возможны ли множественные пути из S в T?   -  person bjskishore123    schedule 14.11.2010
comment
вам просто нужно найти один путь для решения проблемы, я думаю, это то, о чем говорят вопросы.   -  person catvsrat    schedule 15.11.2010

Ответы (3)


arrow_upward
2
arrow_downward

Один из способов найти путь:

  1. Имейте очередь ячеек для проверки и количество шагов для каждой ячейки оттуда до места назначения.
  2. Установите счетчик конечной ячейки на 0 и добавьте его в очередь.
  3. While the queue is not empty:
    1. Get a cell from the queue.
    2. Для каждой свободной соседней ячейки сравните количество текущей ячейки + 1 с количеством соседней ячейки. Если меньше, или если соседняя ячейка еще не имеет счетчика, установите счетчик соседней ячейки равным счетчику текущей ячейки + 1, а затем добавьте соседнюю ячейку в очередь.

Как только очередь станет пустой, каждая свободная ячейка в лабиринте (в которую можно попасть из пункта назначения) будет иметь количество шагов кратчайшего пути к пункту назначения. Если в ячейке нет счетчика, пути от нее к месту назначения нет.

Если в начальной ячейке есть счетчик,

  1. Получите количество начальных ячеек.
  2. Проверьте каждую соседнюю ячейку на количество (count - 1). Будет будет один, и это следующий шаг на пути. Запишите направление к этой ячейке, а затем получите эту ячейку, и если это не пункт назначения, повторите шаг 2 с этой ячейкой.

Я оставлю это на ваше усмотрение, чтобы понять, как загрузить лабиринт. Это легкая часть всего этого.

person cHao    schedule 14.11.2010
comment
Также известен как Flood Filling, если я не ошибаюсь. Вероятно, самый простой способ решить это я применил еще в старшей школе (после следуют варианты с левой стеной, в которых можно попасть в ловушку). - person Matthieu M.; 14.11.2010

arrow_upward
3
arrow_downward

Если вы не знаете, что искать: http://en.wikipedia.org/wiki/Pathfinding#Sample_algorithm и здесь содержится НАМНОГО больше информации: http://www.astrolog.org/labyrnth/algrithm.htm

person problemofficer    schedule 14.11.2010

arrow_upward
0
arrow_downward

Кода слишком много, чтобы писать здесь, но самый распространенный способ решения лабиринтов — это отправиться в одном направлении, и при каждом правильном повороте, который вы можете сделать, поворачивайте направо.

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

Посмотрите, что вы можете придумать с точки зрения кода, основываясь на этом в качестве отправной точки!

ХТХ, Джеймс

person James King    schedule 14.11.2010
comment
Это также предполагает, что во внешних стенах нет отверстий, кроме начала и выхода, конечно. - person Cascabel; 14.11.2010
comment
С точки зрения графов, этот алгоритм отлично работает для connected, acyclic graphs и ни для каких других типов. - person SingleNegationElimination; 14.11.2010
comment
Джефроми › Верно! TokenMackGuy› Какой пример лабиринта не является связным ациклическим графом? (Моя теория графов слаба) - person James King; 14.11.2010
comment
@James: Скажем, одна из конечных точек находится в середине лабиринта и окружена своего рода подлабиринтом, который вообще не связан с внешней стеной. Можно было бы пройти весь внутренний лабиринт и вернуться туда, где вы начали. (Читайте: лабиринт больше не является ациклическим.) И если вы время от времени не меняете сторону, вы никогда не проберетесь из внешнего лабиринта во внутренний. - person cHao; 14.11.2010
comment
:: кивок :: Да, именно поэтому я сказал, что это гарантированно сработает только в том случае, если начало и выход находятся в одной из окружающих стен. Теперь я знаю официальный термин: связный ациклический граф :) - person James King; 15.11.2010