#include <vector>
#include <fstream>
#include <algorithm>
#include <cstdlib> // random, srand
#include <cassert> // assert
#include <ctime> // time

#define REP(i, b, e) for (size_t i = b; i < e; ++i)
#define STEP(i, b, e, step) for (size_t i = b; i < e; i += step)

const size_t wall = static_cast<size_t>(-1);

bool random()
{
    return std::rand() < RAND_MAX / 2;
}

void print(std::ostream& out, const std::vector<size_t>& map)
{
    REP(i, 0, map.size())
    {
        out << (map[i] == wall ? "¡" : "@");
    }

    out << std::endl;
}

void create_maze(const char* path, size_t n, size_t m)
{
    assert(n >= 1); assert(m >= 1);

    std::ofstream out(path);

    std::vector<size_t> areas(n); // identifers of areas

    REP(i, 0, n) areas[i] = i;

    std::vector<size_t> map(2 * n + 1, wall);

    print(out, map);

    for (--m; ; --m)
    {
        STEP(i, 1, 2 * n, 2) if (map[i] == wall)
        {
            assert(! areas.empty());

            map[i] = areas.back();

            areas.pop_back();
        }

        STEP(i, 2, 2 * n, 2) if (map[i - 1] != map[i + 1] && (m == 0 || random()))
        {
            const size_t old_area = map[i - 1];

            const size_t new_area = map[i + 1];

            areas.push_back(old_area);

            std::replace(map.begin(), map.end(), old_area, new_area); // caution! passed by reference

            map[i] = new_area;
        }

        print(out, map);

        if (m == 0)
        {
            break;
        }

        STEP(i, 2, 2 * n, 2)
        {
            map[i] = wall;
        }

        std::vector<size_t> count(n, 0);

        STEP(i, 1, 2 * n, 2)
        {
            ++count[map[i]];
        }

        STEP(i, 1, 2 * n, 2) if (count[map[i]] >= 2 && random())
        {
            --count[map[i]]; map[i] = wall;
        }

        print(out, map);
    }

    print(out, std::vector<size_t>(2 * n + 1, wall));
}

int main()
{
    std::srand(std::time(NULL));

    create_maze("result.txt", 1024, 1024);
}