// У нас есть лабиринт 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() {
    
}