@Mootfrost
C#, C++, JS, Python

Как правильно пропарсить лабиринт в граф?

У меня есть лабиринт в двумерном массиве. Как мне правильно его превратить в матрицу смежности, если вершины графа - каждый поворот? Вес ребра - расстояние между двумя вершинами. Его тоже надо получить
  • Вопрос задан
  • 170 просмотров
Решения вопроса 3
Alexandroppolus
@Alexandroppolus
кодир
Похоже, тут обычный поиск в ширину. Сначала находишь первую вершину (просмотреть первую строку, потом вторую и т.д., первая попавшаяся звездочка будет поворотом или тупиком). Ну а далее все соседние звездочки - это соседние вершины, либо пути в соседние вершины (то есть в каждую сторону идешь прямо, пока встречаются "транзитные" звездочки, а именно ограниченные решетками или краями карты с двух противоположных сторон, и подсчитываешь длину пути).
Если в лабиринте только одно пространство, то обойдешь всё. Иначе надо после завершения обхода в ширину снова искать неотмеченные вершины.
Ответ написан
Комментировать
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Самое простое - это сделать вершиной каждую клетку и гнать в этом графе поиск в ширину. Можно даже не строить граф явно - а просто при обходе смотреть на четырех соседей и проверять, а не стена ли там, а были ли мы в клетке (x+dx[k], y+dy[k]), и класть координаты в очередь, если надо.

Вы же хотите считать только перекрестки и повороты врешинами. В худшем случае, если поворотов в лабиринте много - это будет даже медленнее обхода в ширину. Потому что он работает за линию, а дейкстра - за O(n log n) в лучшем случае. Плюс там константа больше у этого n log n. Правда, это можно решить если вместо дейкстры использовать обобщенный 0-1-BFS (BFS с ограниченными ребрами - там где много очередей используется). Но реализация будет сильно посложнее простого BFS.

Но если так хотите - то делается это так: Сначала пройдитесь по всем клеткам и занумеруйте те, которые не являются коридором (один сосед, больше двух соседей, или соседи не вдоль одной прямой). Можно в отдельной матрице номера проставить.
Потом пройдитесь по каждому столбцу сверху вниз и по каждой строчке слева направо и храните последнюю встреченную вершину. Если встретили стену - забывайте про эту увиденную раньше врешину. Если встретили просто проход - пропускайте его. Если встретили поворот(вершину) - то создайте ребро между ней и последней увиденной (если она еще в памяти, ведь стена могла ее удалить). Ну и перепишите последнюю увиденную вершину.

Что-то типа такого:
int last_node = 0;
for (i = x_start, j = y_start; i <n && j < m; i+= dx, j+=dy) {
   if (is_wall[i][j]) {
    last_node = -1;
  }  
  if (node_number[i][j] <- 0) continue;
  if (last_node > 0) {
    // добавить ребро между вершинами.
    AddEdge(last_node, node_number[i][j]);
  }
  last_node = node_number[i][j];
}


Тут я просто добавляю ребра в строке или столбце между двумя соседними вершинами.
Ответ написан
Комментировать
@mayton2019
Bigdata Engineer
Мне кажется что ничего не нужно парсить. Можно создать интерфейс графа поверх лабиринта.
Вершины есть. Ребра есть. Все готово для поиска путей и доказательства достижимостей.

Можно только добавить дополнительно на все ребра и вершины возможность ставить метки.
Это как раз для графовых алгоритмов.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 2
@rPman
Лабиринт в форме - ячейка это либо стена либо проход (0/1)?

Заводим класс - 'Вершина графа', ребра которого - его параметры ссылок на Смежные вершины, для каждой стороны вверх, вниз, налево и направо. Если нужно выявление замкнутых подмножеств, то добавляем параметр - номер подмножества (значение 0 - неизвестно)

Создаем временную матрицу для хранения вершин (можно добавить параметр в объект ячейки матрицы, если такой есть) с пустыми/нулевыми значениями
Пробегаем по матрице лабиринта, на каждую пустую ячейку (проход) создаем вершину графа, пусть перебираем матрицу сверху вниз и слева направо, то для каждой такой ячейки смотрим наличие прохода слева и сверху, если есть, добавляем соответственно ссылки на слева и сверху, а для их вершин ссылку на текущую созданную соответственно справа и снизу.

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

В результате когда пройдем по всем ячейкам матрицы, у нас будет готовый список графов, ячейки которого пронумерованы (ну не по порядку, будут пропуски номеров), понадобится еще проход, чтобы записать в список эти группы, и можно удалять временную матрицу вершин
Ответ написан
Комментировать
@AlexSku
Программист по автоматике
На Haskell советуют применять zippers (список пар).
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы