#include <chrono>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <thread>
#include <vector>

struct Maze
{
    enum Cell
    {
        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);
    std::srand(seed);
    // Entrance.
    maze(1, 0) = maze(1, 1) = Maze::PATH;
    // Interior.
    auto cx = 1;
    auto cy = 1;
    auto done = false;
    while (!done)
    {
        // Call callback.
        callback(maze);
        // Find number of neighbors.
        auto n = 0;
        for (auto ny = -2; ny <= 2; ny += 2)
        for (auto nx = -2; nx <= 2; nx += 2)
            if (!nx != !ny)
            if (maze(cx+nx, cy+ny) == Maze::WALL)
                ++n;
        // If we have neighbors, carve path to random one.
        if (n != 0)
        {
            n = std::rand() % n;
            for (auto ny = -2; ny <= 2; ny += 2)
            for (auto nx = -2; nx <= 2; nx += 2)
                if (!nx != !ny)
                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 = true;
        for (auto ry = 1; ry < h && done; ry += 2)
        for (auto rx = 1; rx < w && done; rx += 2)
            if (maze(rx, ry) == Maze::WALL)
                for (auto ny = -2; ny <= 2 && done; ny += 2)
                for (auto nx = -2; nx <= 2 && done; nx += 2)
                    if (!nx != !ny)
                    if (maze(rx+nx, ry+ny) == Maze::PATH)
                    {
                        cx = rx+nx;
                        cy = ry+ny;
                        done = false;
                    }
    }
    // 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 seed = (unsigned)std::time(nullptr);
        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(1000, 1000, 0);
        auto const t2 = steady_clock::now();
        std::cout << duration_cast<milliseconds>(t2 - t1).count() << "ms\n";
    }
}