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