#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;
}