#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; // Лабиринт
};