/* 迷路プログラム */
/* 言語:C */

#include<stdio.h>
#include<stdlib.h>

/*ブール値の定義*/
#define TRUE 1
#define FALSE 0
typedef int BOOL;

#define YOKO 7/*横幅*/
#define TATE 7/*縦幅*/

/*迷路データ(0:通れる道,1:壁,2:スタート,3:ゴール,4:通った道,5:正解ルート)*/
int maze[TATE][YOKO]={
	{1,1,1,1,1,1,1},
	{1,0,0,0,0,2,1},
	{1,0,0,0,0,1,1},
	{1,0,0,0,0,0,1},
	{1,0,0,0,0,0,1},
	{1,0,0,0,0,0,1},
	{1,1,1,1,1,1,1}
};

/*外部変数*/
int sx,sy;/*スタート地点*/
int gx=-1,gy=-1;/*ゴール地点*/
int sp,ri[100],rj[100];/*スタック*/
char chara[6][3]={"　","■","Ｓ","Ｇ","△","○"};/*キャラ*/
int count,anscount;/*行き止まりになった回数をカウント*/
int end=FALSE;/*終了判定(yes=true,no=false)*/

/*データ読み込み関数*/
void Input(char *file){
	FILE *fin;
	int i,j,c;
	if((fin=fopen(file,"r"))==NULL){
		fprintf(stderr,"Input error [%s]\n",file);
		return;
	}
	i=j=0;
	while((c=fgetc(fin))!=EOF){
		if(c=='\n')continue;
		maze[i][j]=c-'0';
		if(++j >= YOKO){
			j=0;
			if(++i >= TATE){break;}
		}
	}
	fclose(fin);
}

/*初期化*/
void Init(){
	int i,j;
	for(i=0;i<TATE;i++){
		for(j=0;j<YOKO;j++){
			if(maze[i][j]==2){
				sx=j;sy=i;
				maze[i][j]=0;
			}else if(maze[i][j]==3){
				gx=j;gy=i;
				maze[i][j]=0;
			}else if(maze[i][j]==4||maze[i][j]==5){
				maze[i][j]=0;
			}
		}
	}
	end=FALSE;
	count=anscount=0;
}

/*表示関数*/
void Disp(){
	int i,j;
	printf("   ");
	for(i=0;i<YOKO;i++)printf("%2d",i);
	putchar('\n');

	for(i=0;i<TATE;i++){
		printf("%2d ",i);
		for(j=0;j<YOKO;j++){
			if(i==sy&&j==sx)printf(chara[2]);
			else if(i==gy&&j==gx)printf(chara[3]);
			else printf(chara[maze[i][j]]);
		}
		putchar('\n');
	}
	putchar('\n');
}

/*編集関数*/
void Edit(){
	int i,j;
	char str[4];
	printf("tate-->");
	i=atoi(gets(str));
	printf("yoko-->");
	j=atoi(gets(str));
	printf("value(0:road,1:wall,2:start,3:goal)-->");
	gets(str);
	maze[i][j]=str[0]-'0';
}

/*全ての道が塞がっているかチェック関数*/
BOOL Check(){
	int i,j;
	for(i=0;i<TATE;i++){
		for(j=0;j<YOKO;j++){
			if(maze[i][j]==0)return FALSE;
		}
	}
	return TRUE;
}

/*訪問関数(ゴールに達成したらtrueを返す)*/
BOOL Solve(int tate,int yoko){
	int i;

	maze[tate][yoko]=4;/*道に印を付ける*/
	/*スタックに積む*/
	ri[sp]=tate;
	rj[sp]=yoko;
	sp++;

	/*ゴールした場合*/
	if(tate==gy&&yoko==gx){
		/*経路表示*/
		for(i=0;i<sp;i++){printf("(%d,%d)",ri[i],rj[i]);}
		putchar('\n');
		end=TRUE;
	}

	if(!end && maze[tate][yoko+1]==0)Solve(tate,yoko+1);
	if(!end && maze[tate+1][yoko]==0)Solve(tate+1,yoko);
	if(!end && maze[tate][yoko-1]==0)Solve(tate,yoko-1);
	if(!end && maze[tate-1][yoko]==0)Solve(tate-1,yoko);

	/*行く道がない場合*/
	count++;
	/*全ての道が塞がっているかチェック(塞がっていた場合が解となる)*/
	if(Check()==TRUE){anscount++;}

	sp--;/*スタックから捨てる*/
	maze[tate][yoko]=0;/*印を消す*/

	/*ゴールした場合、経路保存*/
	if(end)maze[tate][yoko]=5;

	return end;
}

/*メイン関数*/
int main(int argc,char *argv[]){
	char str[4];/*バッファ*/
	char file[16];/*データファイル*/

	/*データ指定起動*/
	if(argc!=1){
		Input(argv[1]);/*データ読み込み*/
	}
	while(TRUE){
		Init();/*初期化*/
		printf("[d]isp,[s]olve,[e]dit,[l]oad,[q]uit -->");
		gets(str);
		switch(str[0]){
		case 'd':Disp();break;
		case 's':
			if(Solve(sy,sx)==FALSE){puts("解けない迷路");}
			else{Disp();}
			if(!end)printf("%dパターン中、一筆書き経路は%d通り。\n",count,anscount);
			break;
		case 'e':Edit();break;
		case 'l':
			printf("filename-->");
			gets(file);
			if(file[0]!='\0')Input(file);
			break;
		case 'q':return 0;
		}
	}
}

/*----------------実行結果----------------

[d]isp,[s]olve,[e]dit,[l]oad,[q]uit -->d
    0 1 2 3 4 5 6
 0 ■■■■■■■
 1 ■　　　　Ｓ■
 2 ■　　　　■■
 3 ■　　　　　■
 4 ■　　　　　■
 5 ■　　　　　■
 6 ■■■■■■■

[d]isp,[s]olve,[e]dit,[l]oad,[q]uit -->s
解けない迷路
43207パターン中、一筆書き経路は0通り。
[d]isp,[s]olve,[e]dit,[l]oad,[q]uit -->e
tate-->2
yoko-->5
value(0:road,1:wall,2:start,3:goal)-->0
[d]isp,[s]olve,[e]dit,[l]oad,[q]uit -->d
    0 1 2 3 4 5 6
 0 ■■■■■■■
 1 ■　　　　Ｓ■
 2 ■　　　　　■
 3 ■　　　　　■
 4 ■　　　　　■
 5 ■　　　　　■
 6 ■■■■■■■

[d]isp,[s]olve,[e]dit,[l]oad,[q]uit -->s
解けない迷路
153745パターン中、一筆書き経路は824通り。
[d]isp,[s]olve,[e]dit,[l]oad,[q]uit -->l
filename-->maze.txt
[d]isp,[s]olve,[e]dit,[l]oad,[q]uit -->d
    0 1 2 3 4 5 6
 0 ■■■■■■■
 1 ■Ｇ■■　Ｓ■
 2 ■　■　■　■
 3 ■　　　■　■
 4 ■■■　■　■
 5 ■　　　　　■
 6 ■■■■■■■

[d]isp,[s]olve,[e]dit,[l]oad,[q]uit -->s
(1,5)(2,5)(3,5)(4,5)(5,5)(5,4)(5,3)(4,3)(3,3)(3,2)(3,1)(2,1)(1,1)
    0 1 2 3 4 5 6
 0 ■■■■■■■
 1 ■Ｇ■■　Ｓ■
 2 ■○■　■○■
 3 ■○○○■○■
 4 ■■■○■○■
 5 ■　　○○○■
 6 ■■■■■■■

[d]isp,[s]olve,[e]dit,[l]oad,[q]uit -->q
Press any key to continue

---------------------------------------*/