// Resolver el laberinto: de pasajes a un grafo, y buscar con BFS y con DFS. Completen los tres.
#ifndef SOLVER_H
#define SOLVER_H

#include <algorithm>
#include <cstddef>
#include <queue>
#include <utility>
#include <vector>

#include "graph.h"
#include "maze.h"
#include "not_implemented.h"

// Lo que devuelve una búsqueda:
// - path: del origen al destino, los dos incluidos. Vacío si no se llega.
// - visited: los nodos marcados, en el orden en que se marcaron, sin repetir.
// Las dos búsquedas marcan igual y paran igual: se detienen apenas marcan el destino.
struct SearchResult {
    std::vector<int> path;
    std::vector<int> visited;
};

// Paso 3: un nodo por celda, y una arista sin peso por cada pasaje, en el orden de maze.passages().
inline Graph maze_graph(const Maze& maze) {
    (void)maze;
    not_implemented("maze_graph");
}

// Paso 3: BFS que marca al meter a la cola y guarda de dónde se llegó. Recorre los vecinos en el
// orden de la lista. El camino sale de los padres, y hay que darle la vuelta.
inline SearchResult bfs_search(const Graph& graph, int source, int target) {
    (void)graph;
    (void)source;
    (void)target;
    not_implemented("bfs_search");
}

// Paso 3: DFS con pila propia, no recursivo: una prueba corre un pasillo largo con poca pila.
// Recorre los vecinos en el orden de la lista, como lo haría la versión recursiva.
inline SearchResult dfs_search(const Graph& graph, int source, int target) {
    (void)graph;
    (void)source;
    (void)target;
    not_implemented("dfs_search");
}

#endif