#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_;}
        Point2 operator + (Point2& in){
            Point2 T;
            T.x= x+in.x;
            T.y= y+in.y;
            return T;
        }
    };
    
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(){
        Point2 T={rand()%Width(),rand()%Height()};
        Generate(T);
    }
    
    void Generate(Point2 Pos,bool IsDifferent = false){//非再起版。
        static Point2 V[]={{-1,0},{0,1},{1,0},{0,-1}};
        Uni F;
        F.Int=0x03020100;
        std::vector<Point2> stp;//スタック。
        stp.push_back(Pos);
        std::random_shuffle(F.Char,F.Char+4);
        while(stp.size() != 0){
            Pos = stp.back();stp.pop_back();
            if(!IsDifferent) F.Int=0x03020100;
            std::random_shuffle(F.Char,F.Char+4);
                for(int i=0;i<4;i++){
                    if(ToVisit(Pos,V[F.Char[i]],F.Char[i])) stp.push_back(Pos +V[F.Char[i]]);
                }
        }
        return ;
    }
    
    bool ToVisit(Point2 Base,Point2 To,int Command){
        if(!CanVisit(Base.x,Base.y)) return false;
        if(!CanVisit(Base.x+To.x,Base.y+To.y)) return false;
        //if(AlreadyVisit(Base.x,Base.y)) return false;
        if(AlreadyVisit(Base.x+To.x,Base.y+To.y)) return false;
        MarkVisit(Base.x,Base.y);
        MarkVisit(Base.x+To.x,Base.y+To.y);
        EraseWall(Base,To,Command);
        return true;
    }
};
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));
    clock_t start,end;
    start = clock();
    //Maze_t m(12,5);
//    Maze_t m(19,11);
//    Maze_t m(19,100);
    Maze_t m(1024,1024);
    end = clock();
    printf("Generate at [%d]clock!\n",end-start);
    PrintMaze2(m);
    return 0;
}