// El laberinto: una cuadrícula de celdas con paredes entre vecinas. Completen generate_maze; lo demás ya viene hecho.
#ifndef MAZE_H
#define MAZE_H

#include <cassert>
#include <cstddef>
#include <cstdint>
#include <random>
#include <string>
#include <utility>
#include <vector>

#include "not_implemented.h"
#include "union_find.h"

// Una pared separa dos celdas vecinas, con a < b.
struct Wall {
    int a;
    int b;
};

// Baraja con Fisher-Yates sobre números del generador. No usa std::shuffle: su resultado depende de
// la biblioteca, y así la misma semilla da el mismo laberinto en cualquier máquina.
inline void shuffle_walls(std::vector<Wall>& walls, std::mt19937& rng) {
    for (std::size_t i = walls.size(); i > 1; i--) {
        std::swap(walls[i - 1], walls[rng() % i]);
    }
}

// Las celdas se numeran por filas: la celda de la columna x y la fila y es y * width + x.
// Invariantes: cada pasaje une dos celdas vecinas, y ninguno se repite.
class Maze {
public:
    Maze(int width, int height) : width_(width), height_(height) {
        assert(width > 0 && height > 0);
    }

    int width() const { return width_; }
    int height() const { return height_; }
    int cell_count() const { return width_ * height_; }
    int cell(int x, int y) const { return y * width_ + x; }

    // Los pasajes abiertos, en el orden en que se abrieron.
    const std::vector<Wall>& passages() const { return passages_; }

    bool is_open(int a, int b) const {
        for (const Wall& wall : passages_) {
            if ((wall.a == a && wall.b == b) || (wall.a == b && wall.b == a)) {
                return true;
            }
        }
        return false;
    }

    void open(const Wall& wall) { passages_.push_back(wall); }

    // Todas las paredes entre celdas vecinas, abiertas o no: de izquierda a derecha y de arriba abajo.
    std::vector<Wall> all_walls() const {
        std::vector<Wall> walls;
        for (int y = 0; y < height_; y++) {
            for (int x = 0; x < width_; x++) {
                if (x + 1 < width_) {
                    walls.push_back({cell(x, y), cell(x + 1, y)});
                }
                if (y + 1 < height_) {
                    walls.push_back({cell(x, y), cell(x, y + 1)});
                }
            }
        }
        return walls;
    }

    // Dibuja el laberinto. Marca con . los visitados y con * el camino; el primero y el último del
    // camino salen como S y E.
    std::string render(const std::vector<int>& path = {}, const std::vector<int>& visited = {}) const {
        std::vector<char> mark(cell_count(), ' ');
        for (int node : visited) {
            mark[node] = '.';
        }
        for (int node : path) {
            mark[node] = '*';
        }
        if (!path.empty()) {
            mark[path.front()] = 'S';
            mark[path.back()] = 'E';
        }
        std::vector<char> open_right(cell_count(), 0);
        std::vector<char> open_down(cell_count(), 0);
        for (const Wall& wall : passages_) {
            (wall.b == wall.a + 1 ? open_right : open_down)[wall.a] = 1;
        }
        std::string text;
        for (int x = 0; x < width_; x++) {
            text += "+--";
        }
        text += "+\n";
        for (int y = 0; y < height_; y++) {
            text += "|";
            for (int x = 0; x < width_; x++) {
                text += mark[cell(x, y)];
                text += mark[cell(x, y)];
                text += open_right[cell(x, y)] ? ' ' : '|';
            }
            text += "\n+";
            for (int x = 0; x < width_; x++) {
                text += open_down[cell(x, y)] ? "  +" : "--+";
            }
            text += "\n";
        }
        return text;
    }

private:
    int width_;
    int height_;
    std::vector<Wall> passages_;
};

// Abre hasta `extra` paredes más, al azar: aparecen ciclos. Devuelve cuántas abrió.
inline int open_extra_walls(Maze& maze, int extra, std::mt19937& rng) {
    std::vector<char> is_open_right(maze.cell_count(), 0);
    std::vector<char> is_open_down(maze.cell_count(), 0);
    for (const Wall& wall : maze.passages()) {
        (wall.b == wall.a + 1 ? is_open_right : is_open_down)[wall.a] = 1;
    }
    std::vector<Wall> closed;
    for (const Wall& wall : maze.all_walls()) {
        bool is_right = wall.b == wall.a + 1;
        if (!(is_right ? is_open_right : is_open_down)[wall.a]) {
            closed.push_back(wall);
        }
    }
    shuffle_walls(closed, rng);
    int opened = 0;
    for (const Wall& wall : closed) {
        if (opened == extra) {
            break;
        }
        maze.open(wall);
        opened++;
    }
    return opened;
}

// Paso 2: abre paredes hasta dejar un laberinto perfecto. Tomen todas las paredes, barájenlas con
// shuffle_walls, recórranlas en ese orden, y abran cada una que separe dos regiones distintas.
inline void generate_maze(Maze& maze, std::mt19937& rng) {
    (void)maze;
    (void)rng;
    not_implemented("generate_maze");
}

#endif