File:MAZE 30x20 Prim.ogv

#include <iostream>
#include <queue>
#include <random>
#include <utility>
#include <vector>
#include <cstdio>

using namespace std;

const int xsize = 20;
const int ysize = 30;

int main() {
    random_device rd;
    mt19937 en(rd());
    uniform_real_distribution<double> uni(0,1);

    vector<int> v(xsize*ysize, 0);
    vector<int> w(xsize*ysize*2, 1);
    vector<vector<pair<double, pair<int, int>>>> e(xsize*ysize);

    for(int i=0; i<xsize; i++) {
        for(int j=0; j<ysize; j++) {
            int k = i*ysize + j;
            if(i>0) e[k].push_back(make_pair(uni(en), make_pair(k, (i-1)*ysize + j)));
            if(j>0) e[k].push_back(make_pair(uni(en), make_pair(k, i*ysize + (j-1))));
            if(i<xsize-1) e[k].push_back(make_pair(uni(en), make_pair(k, (i+1)*ysize + j)));
            if(j<ysize-1) e[k].push_back(make_pair(uni(en), make_pair(k, i*ysize + (j+1))));
        }
    }
    priority_queue <pair<double, pair<int, int>>> frontier;
    int x = 0, y = 0;
    v[x*ysize + y] = 1;
    for(auto k : e[0]) {
        frontier.push(k);
    }
    while(!frontier.empty()) {
        auto z = frontier.top();
        frontier.pop();
        int a = z.second.first;
        int b = z.second.second;
        if(v[b]) continue;
        v[b] = 2;
        int aa = min(a,b);
        int bb = max(a,b);
        if(bb-aa == 1) {
            w[2*aa] = 0;
        } else {
            w[2*aa+1] = 0;
        }
        for(auto k : e[b]) {
            if(!v[k.second.second]) {
                frontier.push(k);
            }
        }
        // print the thing lol
        for(int j=0; j<2*ysize+1; j++) {
            cout << "1 ";
        }
        for(int i=0; i<xsize; i++) {
            cout << endl << "1 ";
            for(int j=0; j<ysize; j++) {
                cout << "102"[v[i*ysize + j]] << " " << "01"[w[2*(i*ysize + j)]] << " ";
            }
            cout << endl << "1 ";
            for(int j=0; j<ysize; j++) {
                cout << "01"[w[2*(i*ysize + j)+1]] << " 1 ";
            }
        }
        cout << endl;
        v[b] = 1;
    }
}