Pasted

#pragma once
#include <iostream>
 
#include <vector>
#include <queue>
 
#define WALL false
#define WAY true
 
using namespace std;
 
// Нужно, чтобы добавлять координату пути
// В очередь или вектор
struct Vector2 {
    int x;
    int y;
    Vector2(int x, int y) : x(x), y(y) {};
};
 
//
// Класс лабиринта
// TODO: добавить описание
//
class Labyrinth {
public:
    // X - кол-во строк
    // Y - кол-во столбцов
    Labyrinth(int max_x, int max_y) : x(max_x), y(max_y) {
        // Инициализируем матрицу лабиринта
        labyrinth.resize(max_x);
        for (int i = 0; i < max_x; ++i) {
            labyrinth[i].resize(max_y);
            for (int j = 0; j < max_y; ++j) {
                labyrinth[i][j] = WAY;
            }
        }
    }
 
    void setWall(int x, int y) {
        labyrinth[x][y] = WALL;
    }
 
    void deleteWall(int x, int y) {
        labyrinth[x][y] = WAY;
    }
 
    // Поиск выхода в лабиринте из точки start_x, start_y
    // Используется волновой алгоритм
    //
    // x, y - начальная позиция
    void findExit(int start_x, int start_y) {
        // Инициализируем матрицу размера x*y, заполненную -1 
        // где хранится расстояние от старта до текущей клетки
        vector<vector<int>> distantion(x, vector<int>(y, -1));
        distantion[start_x][start_y] = 0;
 
        // Очередь, в которой будут вершины, которые нужно обойти
        queue<Vector2> queue;
        queue.push(Vector2(start_x, start_y));
 
        while (!queue.empty()) {
            // Вынесем функцию для обработки вершины
            // в встраиваемую функцию, чтобы не мозолило глаза
            if (nextStep(queue, distantion)) {
                Vector2 finish = queue.front();
                printWay(distantion, finish.x, finish.y);
                cout << endl;
                return;
            }
        }
    }
 
    // Функция возвращает true, если вершина найдена
    // Vector2 вершины находится в начале очереди
    inline bool nextStep(queue<Vector2> &queue, vector<vector<int>> &distantion) {
        // Обрабатываемемая вершина
        Vector2 position = queue.front();
        // Если мы нашли выход из лабиринта
        if (position.x == 0 || position.x == x ||
            position.y == 0 || position.y == y) {
            return true;
        }
        queue.pop();
        // Дистанция от старта для текущей вершины
        int current_distantion = distantion[position.x][position.y];
 
        // Проверяем четыре вершины (выше, ниже, правее, левее)
        // На то, нужно ли их просматривать (проходить)
        checkPositioin(queue, distantion, current_distantion, position.x, position.y + 1);
        checkPositioin(queue, distantion, current_distantion, position.x, position.y - 1);
        checkPositioin(queue, distantion, current_distantion, position.x + 1, position.y);
        checkPositioin(queue, distantion, current_distantion, position.x - 1, position.y);
 
        return false;
    }
 
    // Смотрим, если вершина - путь, и расстояние от нее до старта больше, чем
    // расстояние от старта, до соседней вершины - то 'еще раз проходим эту вершину'
    // так как найден более короткий путь для нее
    inline void checkPositioin(queue<Vector2> &queue, vector<vector<int>> &distantion, int current_distantion, int x, int y) {
        if (labyrinth[x][y] == WAY && (distantion[x][y] == -1 || distantion[x][y] > current_distantion)) {
            queue.push(Vector2(x, y));
            distantion[x][y] = current_distantion + 1;
        }
    }
 
    // Выбрать среди соседних ячейку,
    // помеченную числом на 1 меньше числа в текущей ячейке
    // и перейти в выбранную ячейку
    inline void printWay(vector<vector<int>> &distantion, int x, int y) {
        int need_distance = distantion[x][y] - 1;
        if (need_distance == -1) return; // Конец цикла, если текущая клетка - старт
        // Для четырех вершин (выше, ниже, правее, левее) смотрим
        if (y != this->y && distantion[x][y + 1] == need_distance) {
            printWay(distantion, x, y + 1);
            cout << "L";
        } else if (y != 0 && distantion[x][y - 1] == need_distance) {
            printWay(distantion, x, y - 1);
            cout << "R";
        } else if (x != this->x && distantion[x + 1][y] == need_distance) {
            printWay(distantion, x + 1, y);
            cout << "U";
        } else if (x != 0 && distantion[x - 1][y] == need_distance) {
            printWay(distantion, x - 1, y);
            cout << "D";
        }
    }
 
private:
    int x; // кол-во строк
    int y; // кол-во столбцов
 
    vector<vector<bool>> labyrinth; // Лабиринт
};