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

Question

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

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

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

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

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

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

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

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

Answer 1

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

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

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

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

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

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

Answer 2

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

Answer 3

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

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

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

Х-е, Джеймс