// Geografía generalizada: una ficha empieza en el nodo de partida, que cuenta como visitado.
// Los jugadores se turnan para moverla por una arista a un nodo no visitado. Pierde quien no
// puede mover.
//
// La búsqueda es recursiva y en profundidad. Guarda solo el camino actual: `visited` marca
// los nodos del camino y nada más, porque cada llamada desmarca su nodo al volver.
#ifndef GEOGRAPHY_H
#define GEOGRAPHY_H

#include <algorithm>
#include <vector>

#include "graph.h"

struct GameStats {
    long long calls = 0;  // posiciones examinadas: el tiempo
    int max_path = 0;     // el camino más largo que estuvo guardado, en nodos: el espacio
};

// ¿Tiene estrategia ganadora quien debe mover con la ficha en `current`?
// `visited` marca los nodos del camino, incluido `current`; `path_length` es cuántos son.
inline bool mover_wins(const Graph& g, int current, std::vector<bool>& visited, int path_length, GameStats& stats) {
    stats.calls++;
    stats.max_path = std::max(stats.max_path, path_length);
    for (int next : g.edges[current]) {
        if (visited[next]) {
            continue;
        }
        visited[next] = true;
        bool rival_wins = mover_wins(g, next, visited, path_length + 1, stats);
        visited[next] = false;  // al volver, el espacio queda libre para la jugada siguiente
        if (!rival_wins) {
            return true;  // una jugada que deja al rival sin estrategia: no hace falta mirar más
        }
    }
    return false;  // no hay jugadas, o todas le dejan una estrategia ganadora al rival
}

// El resultado para el primer jugador: -1 si no tiene estrategia ganadora y, si la tiene,
// una primera jugada ganadora (la primera que aparece en la lista de aristas).
inline int winning_first_move(const Graph& g, GameStats& stats) {
    std::vector<bool> visited(g.nodes.size(), false);
    visited[g.start] = true;
    stats.calls++;
    stats.max_path = std::max(stats.max_path, 1);
    for (int next : g.edges[g.start]) {
        if (visited[next]) {
            continue;
        }
        visited[next] = true;
        bool rival_wins = mover_wins(g, next, visited, 2, stats);
        visited[next] = false;
        if (!rival_wins) {
            return next;
        }
    }
    return -1;
}

inline bool first_player_wins(const Graph& g) {
    GameStats stats;
    return winning_first_move(g, stats) != -1;
}

// El mismo resultado por otro camino, para las pruebas: una tabla con una casilla por cada
// par (conjunto de visitados, nodo actual). Son 2^n · n casillas: tiempo y espacio exponenciales.
// Solo para grafos de hasta 20 nodos.
inline bool first_player_wins_by_table(const Graph& g) {
    int n = static_cast<int>(g.nodes.size());
    // memo[mask * n + v]: 0 sin calcular, 1 gana quien mueve, 2 pierde.
    std::vector<char> memo((std::size_t{1} << n) * static_cast<std::size_t>(n), 0);
    struct Solver {
        const Graph& g;
        int n;
        std::vector<char>& memo;
        bool wins(unsigned mask, int v) {
            char& cell = memo[static_cast<std::size_t>(mask) * static_cast<std::size_t>(n) + static_cast<std::size_t>(v)];
            if (cell != 0) {
                return cell == 1;
            }
            bool result = false;
            for (int next : g.edges[v]) {
                if ((mask >> next) & 1U) {
                    continue;
                }
                if (!wins(mask | (1U << next), next)) {
                    result = true;
                }
            }
            memo[static_cast<std::size_t>(mask) * static_cast<std::size_t>(n) + static_cast<std::size_t>(v)] = result ? 1 : 2;
            return result;
        }
    };
    Solver solver{g, n, memo};
    return solver.wins(1U << g.start, g.start);
}

#endif
