0

Требуется написать алгоритм генерации лабиринта размером 10x10 и реализовать интерфейс прохождения кратчайшего пути между двумя точками. Обозначения: "# - стена . - дорога @ - начало маршрута X - конец маршрута"

public interface Navigator {

char[][] searchRoute(char[][] map);
}

Если маршрут проложить невозможно, метод searchRoute должен возвращать null. Пример: ввод:

...@.     или    ..X..
.####            #####
.....            .....
####.            .@...
.X...            .....

вывод:

+++@.     или     null
+####
+++++
####+
.X+++

Понимаю, что тема не новая, но подходящих решений в интернете я так и не нашел. Сложные алгоритмы генерации лабиринтов не совсем подходят, т.к. они предполагают обязательное наличие выхода из лабиринта. Мне же нужно заполнить поле 10x10 двумя символами в рандомном порядке и уже в полученном поле искать маршрут между двумя точками. А дальше чем заполнение массива только одним символом я продвинуться не могу.

2
  • 7
    Если не нашли решения - напишите своё. Сдаётся мне, в этом и есть суть этой (учебной?) задачи: не найти в интернете, а придумать и реализовать своё решение.
    – Regent
    16 мар 2018 в 8:21
  • Генерация лабиринтов и волновой алгоритм. Может поможет 16 мар 2018 в 8:39

1 ответ 1

1

Воспользуйтесь алгоритмом A* для поиска пути. И генерации лабиринта.

Суть простая. Заполняете поле случайными "весами". По алгоритму, ищете 2-3 оптимальных пути. Их делаете неприкасаемыми, а остальное поле заполняете как угодно. Но правда маршрут всегда можно будет проложить.

1
  • Благодарю за советы в комментариях и ответ. Но они мне не помогли. У меня не получается заменить один символ другим в рандомном порядке во всем массиве. 19 мар 2018 в 9:17

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.