#include"stdio.h"
#define N 10
int c=0;
typedef struct {int r;int c;} postype;//坐標類型
void print(int  maze[][N]) //打印迷宮
{
	int i,j;
	for(i=0;i<N;i++)
	{
		printf("\n");
        for(j=0;j<N;j++)
			printf("%-4d", maze[i][j]);
	}
}
void mazepath(int m[][N], postype curpos, postype end , int count)
{//求當前信置（即：第count步）開始到出口的路徑
	int i,j,k,x,y;
	postype s;
	i=curpos.r; j=curpos.c;
	m[i][j]=count;
	if(i==end.r&&j==end.c) { c++; print(m);getchar();}//如果到出口，則輸出
	else //試探當前位置的四個方向
	{
		for(k=1;k<=4;k++)
		{
			x=i;y=j;
			switch(k){
			case 1: y++;break;
			case 2: x++;break;
			case 3: x--;break;
			case 4: y--;
			}
			if (m[x][y]==0) { s.r=x; s.c=y; mazepath(m,s,end,count+1);}
		}
	}
	m[i][j]=0;//退回一步
}
void main()
{
	int maze[N][N]={{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},{-1,0,0,-1,0,0,0,-1,0,-1},
	{-1,0,0,-1,0,0,0,-1,0,-1},{-1,0,0,0,0,-1,-1,0,0,-1},{-1,0,-1,-1,-1,0,0,0,0,-1},
	{-1,0,0,0,-1,0,0,0,0,-1},{-1,0,-1,0,0,0,-1,0,0,-1},{-1,0,-1,-1,-1,0,-1,-1,0,-1},
	{-1,-1,0,0,0,0,0,0,0,-1},{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}};
	int count=1;
	postype start,end;
    start.r=start.c=1; end.r=end.c=8;
	print(maze); 
	//getchar();//為了觀察迷宮，讓輸出有所停頓
	mazepath(maze,start,end,count);
	printf("c=%d\n",c);
}