/* maze.h : 迷路アルゴリズム関数定義部
（漢字コードを使用環境に合わせてください。）

K. Shiota
2005.6.6
2005.6.10 version
*/

/* 迷路の縦横の最大サイズ
   MAXMAZESIZE^2 は MAXORDER を超えないこと */
#ifndef MAXMAZESIZE
#define MAXMAZESIZE 16
#endif

/* 迷路を表す構造体の定義 */
/* 縦サイズ = row、横サイズ = col、セルの隣接状況を表すグラフ = g */
/* セル (i,j) <-> g の col*i+j 番目の node */
typedef struct {
	int row,col;
	Graph g;
} Maze;

/* m × n のランダムな迷路を生成する */
Maze GenerateMaze(int m, int n)
{
	Maze ma;
	int i,j,k,r,p,q;
	char x[MAXMAZESIZE][MAXMAZESIZE];
	
	ma.g=EmptyGraph(m*n);	// ma.g の初期値は空グラフ
	ma.row=m;
	ma.col=n;
	for(i=0;i<m;i++) for(j=0;j<n;j++) x[i][j]=0;	
	x[0][0]=1;	// セル (i,j) は(0,0) のみ登録済み
	r=m*n-1;	// 残り r 個のセルを結合してゆく
	while(r>0){
		i=rand()%m;
		j=rand()%n;
		k=rand()%4;
		switch(k){
			case 0: if(i>0 && x[i][j]==0 && x[i-1][j]==1){
					p=(i-1)*n+j;
					q=i*n+j;
					ma.g.adj[p][q]=1;
					ma.g.adj[q][p]=1;
					x[i][j]=1;
					r--;
					break;
				}	// 北のセルと結ぶ
			case 1: if(j>0 && x[i][j]==0 && x[i][j-1]==1){
					p=i*n+(j-1);
					q=i*n+j;
					ma.g.adj[p][q]=1;
					ma.g.adj[q][p]=1;
					x[i][j]=1;
					r--;
					break;
				}	// 西のセルと結ぶ
			case 2: if(i<m-1 && x[i][j]==0 && x[i+1][j]==1){
					p=(i+1)*n+j;
					q=i*n+j;
					ma.g.adj[p][q]=1;
					ma.g.adj[q][p]=1;
					x[i][j]=1;
					r--;
					break;
				}	// 南のセルと結ぶ
			case 3: if(j<n-1 && x[i][j]==0 && x[i][j+1]==1){
					p=i*n+(j+1);
					q=i*n+j;
					ma.g.adj[p][q]=1;
					ma.g.adj[q][p]=1;
					x[i][j]=1;
					r--;
					break;
				}	// 東のセルと結ぶ
		}
	}
	return ma;
}

/* 迷路を画面に出力する */
void WriteMaze(Maze m)
{
	int i,j;
	char x[128][128];
	
	for(i=0;i<=2*m.row;i++) 
		for(j=0;j<=2*m.col;j++)
			x[i][j]='#';
	for(i=0;i<m.row;i++) 
		for(j=0;j<m.col;j++)
			x[2*i+1][2*j+1]=' ';
	// 入り口・出口
	x[1][0]=' ';
	x[2*m.row-1][2*m.col]=' ';
	// 南北の仕切
	for(i=1;i<m.row;i++)
		for(j=0;j<m.col;j++)
			if(m.g.adj[(i-1)*m.col+j][i*m.col+j]==1) x[2*i][2*j+1]=' ';
	// 東西の仕切
	for(i=0;i<m.row;i++)
		for(j=1;j<m.col;j++)
			if(m.g.adj[i*m.col+(j-1)][i*m.col+j]==1) x[2*i+1][2*j]=' ';
			
	for(i=0;i<=2*m.row;i++){
		for(j=0;j<=2*m.col;j++){
			if(x[i][j]==' ') printf("　");
			if(x[i][j]=='#') printf("□");
		}
		printf("\n");
	}	
}

/* 迷路と解の path を画面に出力する */
void WriteMazePath(Maze m, List p)
{
	int i,j,k,i1,i2,j1,j2,w;
	char x[128][128];
	
	for(i=0;i<=2*m.row;i++) 
		for(j=0;j<=2*m.col;j++)
			x[i][j]='#';
	for(i=0;i<m.row;i++) 
		for(j=0;j<m.col;j++)
			x[2*i+1][2*j+1]=' ';
	// 入り口・出口
	x[1][0]='.';
	x[2*m.row-1][2*m.col]='.';
	// 南北の仕切
	for(i=1;i<m.row;i++)
		for(j=0;j<m.col;j++)
			if(m.g.adj[(i-1)*m.col+j][i*m.col+j]==1) x[2*i][2*j+1]=' ';
	// 東西の仕切
	for(i=0;i<m.row;i++)
		for(j=1;j<m.col;j++)
			if(m.g.adj[i*m.col+(j-1)][i*m.col+j]==1) x[2*i+1][2*j]=' ';
	for(w=0;w<p.len;w++){
		i=p.mem[w]/m.col;
		j=p.mem[w]%m.col;
		x[2*i+1][2*j+1]='.';
	}
	for(w=1;w<p.len;w++){
		k=p.mem[w-1];
		i1=k/m.col;
		j1=k%m.col;
		k=p.mem[w];
		i2=k/m.col;
		j2=k%m.col;
		if(w>0){
			if(i1<i2) x[2*i2  ][2*j2+1]='.';
			if(i1>i2) x[2*i2+2][2*j2+1]='.';
			if(j1<j2) x[2*i2+1][2*j2  ]='.';
			if(j1>j2) x[2*i2+1][2*j2+2]='.';
		}
	}
			
	for(i=0;i<=2*m.row;i++){
		for(j=0;j<=2*m.col;j++){
			if(x[i][j]==' ') printf("　");
			if(x[i][j]=='#') printf("□");
			if(x[i][j]=='.') printf("・");
		}
		printf("\n");
	}	
}