Решение лабиринта с помощью графика - PullRequest
Новая
       28

Решение лабиринта с помощью графика

0 голосов
/ 14 ноября 2010

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

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

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

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

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

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

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

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

Ответы [ 3 ]

3 голосов
/ 14 ноября 2010

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

2 голосов
/ 14 ноября 2010

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

  1. Есть очередь ячеек для проверки и количество шагов для каждой ячейки оттуда до места назначения.
  2. Установите счетчик конечной ячейки на 0 и добавьте его в очередь.
  3. Пока очередь не пуста:
    1. Получить ячейку из очереди.
    2. Для каждой свободной соседней ячейки сравните число текущей ячейки + 1 с количеством соседних ячеек. Если это меньше, или если соседняя ячейка еще не имеет счетчика, установите счетчик соседней ячейки равным счету текущей ячейки + 1, затем добавьте соседнюю ячейку в очередь.

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

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

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

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

0 голосов
/ 14 ноября 2010

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

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

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

HTH, Джеймс

...