#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#include <stdexcept>
class Maze_t{
    typedef unsigned short MazeElement;
    typedef std::vector<MazeElement> maze_t;
    int Width_,Height_;
    maze_t Data;
    struct Point2{
        int x,y;
        void ToZero(){x=y=0;}
        void Set(int x_, int y_){x=x_; y=y_;}
    };
    
public:
    enum Flags{
        Left=0,
        Up,
        Right,
        Down,
        Visit,
    };
    Maze_t(size_t W,size_t H){
        Create(W,H);
    }
    void Create(size_t W,size_t H){
        Destroy();
        Width_=W;Height_=H;
        Data.resize(W*H);
        std::fill(Data.begin(),Data.end(),int(0));
        Generate();
    }
    void Destroy(){
        Data.clear();
        Width_ = 0;Height_= 0;
    }
    int Width(){ return Width_;}
    int Height(){ return Height_;}
    MazeElement WallInfo(int x, int y){
        if(!CanVisit(x,y)) return 0; 
        return GetElement(x,y);
    }
protected:
    bool CanVisit(int x, int y){
        if(x<0) return false;
        if(y<0) return false;
        if(Width()<=x) return false;
        if(Height()<=y) return false;
        return true;
    }
    bool AlreadyVisit(int x,int y){
        if(!CanVisit(x,y)) return true;
        return GetElement(x,y)>>Visit & 1;
    }
    void MarkVisit(int x,int y){
        if(CanVisit(x,y) == false) return;
        MazeElement& Me = GetElement(x,y);
        Me = Me | 1 << Visit;
    }
    MazeElement& GetElement(int x,int y){
        return Data[Width()*y+x];
    }
    void EraseWall(Point2 Base,Point2 To,int command){
        char Flg1[] = {Left,Up,Right,Down};
        char Flg2[] = {Right,Down,Left,Up};
        MazeElement* p;
        p = &(GetElement(Base.x,Base.y));
        (*p) = (*p) | (1<<Flg1[command]);
        p = &(GetElement(Base.x+To.x,Base.y+To.y));
        (*p) = (*p) | (1<<Flg2[command]);
    }
    struct Uni{
        union{
            int Int;
            char Char[4];
        };
    };
    void Generate(){//メモリ等確保後に実行しないと不整合起こします。つまり単体で使用しないでください。Create関数がエントリです。
        Point2 V[]={{-1,0},{0,1},{1,0},{0,-1}};
        Point2 T={rand()%Width(),rand()%Height()};
        std::vector<Point2> pov;
        std::vector<int> command;
        std::vector<int> rotate;
        Uni U;
        U.Int = 0x03020100;
        std::random_shuffle(U.Char,U.Char+4);
        int i=0;
        pov.push_back(T);
        command.push_back(i);
        rotate.push_back(U.Int);
        MarkVisit(T.x,T.y);
        while(pov.size() != 0){
            T = pov.back();
            i = command.back();
            U.Int = rotate.back();
            for(;i<4;i++){
                if(CanVisit(T.x+V[ U.Char[i]].x,T.y+V[ U.Char[i]].y)){
                    if(AlreadyVisit(T.x+V[ U.Char[i]].x,T.y+V[ U.Char[i]].y)) continue;
                    MarkVisit(T.x+V[ U.Char[i]].x,T.y+V[ U.Char[i]].y);
                    EraseWall(T,V[ U.Char[i]], U.Char[i]);
                    T.x=T.x+V[ U.Char[i]].x;
                    T.y=T.y+V[ U.Char[i]].y;
                    pov.push_back(T);
                    command.push_back(i);
                    rotate.push_back(U.Int);
                    i=0;
                    std::random_shuffle(U.Char,U.Char+4);
                }
            }
            pov.pop_back();
            command.pop_back();
            rotate.pop_back();
        }
    }
};
void PrintMaze(Maze_t& M){
    char W='W',R=' ';
    for(int i=0;i<M.Height();i++){
        for(int k=0;k<3;k++){
            for(int j=0;j<M.Width();j++){
                int wall = M.WallInfo(j,i);
                if(k==0) printf("%c%c%c",W, ((wall>>M.Down)&1)? R:W, W);
                if(k==1) printf("%c%c%c",((wall>>M.Left)&1)? R:W, ((wall>>M.Visit)&1)? R:W, ((wall>>M.Right)&1)? R:W);
                if(k==2) printf("%c%c%c",W, ((wall>>M.Up)&1)? R:W, W);            
            }
            puts("");
        }
    }
}
void PrintMaze2(Maze_t& M){
    char *W="■",*R="　";
    for(int j=0;j<M.Width();j++) printf("%s%s",W,W);
    puts(W);
    for(int i=0;i<M.Height();i++){
        for(int k=1;k<3;k++){
            printf("%s",W);
            for(int j=0;j<M.Width();j++){
                int wall = M.WallInfo(j,i);
                if(k==0) printf("%s%s", ((wall>>M.Down)&1)? R:W, W);
                if(k==1) printf("%s%s", ((wall>>M.Visit)&1)? R:W, ((wall>>M.Right)&1)? R:W);
                if(k==2) printf("%s%s", ((wall>>M.Up)&1)? R:W, W);            
            }
            puts("");
        }
    }
}
int main(){
    //srand(100);
    srand(time(NULL));
    Maze_t m(12,6);
    //Maze_t m(1024,1024);
    PrintMaze2(m);
    return 0;
}