Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // У нас есть лабиринт NxN со стенками и проходами
- // Т.е. для каждой клетки нужно хранить два состояния
- // Пусть стена будет false, а проход - true
- // Тогда хранить лабиринт мы будем в
- // vector<vector<bool>> map
- //
- // Самое простое решение задачи - обход в ширину
- // Но он реализуемых только для графов
- // Поэтому наша задача - сделать что-то подобное графу
- // Но что не будет выглядеть говнокодом
- //
- // 1) Создаём структуру узла графа.
- // struct Node{ short X; short Y }
- // Она нужна для того, чтобы легко было добавлять
- // вершину в очередь вершин, которые нужно пройти
- // и в вектор пройденных вершин
- //
- // 2) Создаём функцию vector<Node> getAdjacentNode(Node &node)
- // для получения списка смежных вершин
- //
- // 3) Создаём массив из пройденных вершин
- // vector<Node> usedNode
- //
- // 4) Нужно создать матрицу, где для каждой вершины будет указан путь, откуда мы к этой вершине добрались
- // Нужно для того, чтобы потом восстановить кратчайший путь
- // vector<vector<Node>> path размером NxN
- #include <iostream>
- #include <vector>
- #include <queue>
- // структура узла
- struct Node {
- short X;
- short Y;
- Node(short X, short Y) {
- this->X = X;
- this->Y = Y;
- }
- }
- // размер лабиринта
- short N;
- // карта лабиринта
- std::vector<std::vector<bool>> map;
- // массив из пройденных вершин
- std::vector<Node> usedNode;
- // вершины, которые будем обходить
- std::queue<Node> queue;
- // для каждой вершины будет указан путь, откуда мы к этой вершине добрались
- std::vector<std::vector<Node>> path;
- // Функция для получения смежных вершин
- // По сути, она смотрит, что если на смежной клетке есть проход
- // то создаём вершину с координатами этого прохода
- std::vector<Node> getAdjacentNode(Node &node) {
- std::vetor<Node> result;
- if (map[node.X][node.Y - 1]) result.push_back(Node(node.X, node.Y - 1));
- if (map[node.X][node.Y + 1]) result.push_back(Node(node.X, node.Y + 1));
- if (map[node.X - 1][node.Y]) result.push_back(Node(node.X - 1, node.Y));
- if (map[node.X + 1][node.Y]) result.push_back(Node(node.X + 1, node.Y));
- return result;
- }
- // Поиск вершины в векторе пройденных вершин
- // Нужна чтобы искать пройдена ли вершина или нет
- bool isUsed(Node &node) {
- for (auto elem = usedNode.begin(); elem != usedNode.end(); ++elem) {
- if (*elem == node) return true;
- }
- return false;
- }
- // Найти кратчайший путь
- // Поиск в ширину
- // Работает за O(n+m), где n - число вершин, m - число ребер
- //
- // Сам алгоритм можно понимать как процесс "поджигания" графа:
- // на нулевом шаге поджигаем только вершину start.
- // На каждом следующем шаге огонь с каждой уже горящей вершины перекидывается на всех её соседей;
- // Т.е. за одну итерацию алгоритма происходит расширение "кольца огня" в ширину на единицу (отсюда и название алгоритма).
- std::vector<Node> shortest_path(Node start) {
- // Добавляем стартовую вершину в начало
- queue.push(start);
- usedNode.push_back(start);
- while (!queue.empty()) {
- Node node = queue.front();
- queue.pop();
- // Говорим, что мы прошли эту вершину
- usedNode.push_back(node);
- // Получаем смежные вершины
- std::vector<Node> adjacent_node = getAdjacentNode(node);
- // Для каждой смежной вершины
- for (auto n = adjacent_node.begin(); n != adjacent_node.end(); ++n) {
- // Если вершина не пройдена
- if (!isUsed(*n)) {
- // TODO:
- // Вот тут по идее должна быть проверка, что
- // Если хотя бы одна координата (Х или У равна 0 или N)
- // То мы должны восстановить путь, и вернуть его из функции
- // Добавляем вершину в конец очереди
- queue.push(*n);
- // Текущая вершина (node) является родителем для смежной вершины. Нужно чтобы восстановить путь
- path[(*n).X][(*n).Y] = node;
- }
- }
- }
- }
- int main() {
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement