#include <chrono>
#include <iostream>
#include <random>
#include <sstream>
#include <thread>
#include <vector>

struct Maze
{
    enum Cell : char
    {
        INVALID,
        EDGE,
        WALL,
        PATH,
    };
    Maze(int w, int h, Cell initial)
    :
        w{w},
        h{h},
        cells(w * h, initial)
    {
        for (auto y = 0; y < h; y += h-1)
        for (auto x = 0; x < w; x += 1)
            cells[w * y + x] = EDGE;
        for (auto y = 0; y < h; y += 1)
        for (auto x = 0; x < w; x += w-1)
            cells[w * y + x] = EDGE;
    }
    Cell & operator ()(int x, int y)
    {
        static auto invalid = INVALID; // Yes, naughty.
        if (0 <= x && x < w && 0 <= y && y < h)
            return cells[w * y + x];
        return invalid;
    }
    void print() const
    {
        std::ostringstream oss;
        for (auto y = 0; y < h; ++y, oss << '\n')
        for (auto x = 0; x < w; ++x)
            oss << (cells[w * y + x] == PATH ? "  " : "██");
        std::cout << oss.str();
    }
    int w;
    int h;
    std::vector<Cell> cells;
};

template<typename C = void(*)(Maze &)>
Maze hunt_and_kill(int w, int h, unsigned seed, C callback = [](Maze &){})
{
    auto maze = Maze(w, h, Maze::WALL);
    auto rand = std::default_random_engine(seed);
    // Entrance.
    maze(1, 0) = maze(1, 1) = Maze::PATH;
    // Interior.
    auto cx = 1; auto rx = 1;
    auto cy = 1; auto ry = 1;
    auto done = false;
    while (!done)
    {
        #define FOR_NEIGHBOR(...) \
            for (auto i = 0; i < 4; ++i) \
            { \
                auto ni = i%2*4-2;   /* -2, +2, -2, +2 */ \
                auto nx = ni* (i/2); /*  0,  0, -2, +2 */ \
                auto ny = ni*!(i/2); /* -2, +2,  0,  0 */ \
                __VA_ARGS__ \
            }
        // Call callback.
        callback(maze);
        // Find number of neighbors.
        auto n = 0;
        FOR_NEIGHBOR(
            if (maze(cx+nx, cy+ny) == Maze::WALL)
                ++n;
        )
        // If we have neighbors, carve path to random one.
        if (n != 0)
        {
            n = std::uniform_int_distribution<>(0, n-1)(rand);
            FOR_NEIGHBOR(
                if (maze(cx+nx, cy+ny) == Maze::WALL && n-- == 0)
                {
                    maze(cx+nx/2, cy+ny/2) = maze(cx+nx, cy+ny) = Maze::PATH;
                    cx = cx+nx;
                    cy = cy+ny;
                }
            )
            continue;
        }
        // No neighbors, done unless there's an uncarved cell to restart at.
        done = [&]() {
            for (; ry < h; ry += 2, rx = 1)
            for (; rx < w; rx += 2)
                if (maze(rx, ry) == Maze::WALL)
                    FOR_NEIGHBOR(
                        if (maze(rx+nx, ry+ny) == Maze::PATH)
                        {
                            cx = rx+nx;
                            cy = ry+ny;
                            return false;
                        }
                    )
            return true;
        }();
        #undef FOR_NEIGHBOR
    }
    // Exit.
    w -= (w + 1) % 2;
    maze(w-2, h-2) = maze(w-2, h-1) = Maze::PATH;
    return maze;
}

int main(int argc, char const * [])
{
    using namespace std::chrono;
    if (argc == 1)
    {
        auto time = system_clock::now().time_since_epoch();
        auto seed = (unsigned)duration_cast<seconds>(time).count();
        auto maze = hunt_and_kill(80/2, 24-1, seed, [](Maze & maze) {
            maze.print();
            std::this_thread::sleep_for(milliseconds(20));
        });
        maze.print();
    }
    else
    {
        auto const t1 = steady_clock::now();
        hunt_and_kill(10000, 10000, 0);
        auto const t2 = steady_clock::now();
        std::cout << duration_cast<milliseconds>(t2 - t1).count() << "ms\n";
    }
}