#include<stdio.h>
#define M 6
#define N 6 
typedef struct {
	int x;
	int y;
	int der;
}node;
typedef struct {
	node maze[100];
	int top;
}stac;

int mg[M+2][N+2]=
{
    {1,1,1,1,1,1,1,1},
    {1,0,0,1,0,0,0,1},
    {1,0,0,1,0,0,0,1},
    {1,0,0,0,0,1,0,1},
    {1,1,1,1,1,0,0,1},
    {1,0,0,0,0,0,0,1},
    {1,0,1,0,0,1,0,1},
    {1,1,1,1,1,1,1,1}
    //{1,1,0,0,0,0,0,0,0,1},
    //{1,1,1,1,1,1,1,1,1,1}
};

void path(int xk,int yk,int m,int n)
{
	stac p;
	int i,find;
	int a,b,der;
	p.top=-1;
	p.top++;
	p.maze[p.top].x=xk;
	p.maze[p.top].y=yk;
	p.maze[p.top].der=0;
	mg[xk][yk]=-1;
	while(p.top>-1)
	{
			a=p.maze[p.top].x;
			b=p.maze[p.top].y;
			der=p.maze[p.top].der;
			find=0;
			if(a==m&&b==n)
			{
				printf("路径：\n");
				for(i=0;i<=p.top;i++)
				{
					printf("( %d , %d )\n",p.maze[i].x,p.maze[i].y);
				}
				return ;
			}
			while(der<=4&&find==0)
			{
				der++;
				switch(der)
					{
						case 1:
							a=p.maze[p.top].x+1;
							b=p.maze[p.top].y;
							break;
						case 2:
							a=p.maze[p.top].x;
							b=p.maze[p.top].y+1;
							break;
						case 3:
							a=p.maze[p.top].x-1;
							b=p.maze[p.top].y;
							break;
						case 4:
							a=p.maze[p.top].x;
							b=p.maze[p.top].y-1;
							break;	
					}
				if(mg[a][b]==0)
				{
					find=1;
				}
			}
			if(find==1)
			{
				p.maze[p.top].der=der;
				p.top++;
				p.maze[p.top].x=a;
				p.maze[p.top].y=b;
				p.maze[p.top].der=0;
				mg[a][b]=-1;
			}
			else
			{
				mg[p.maze[p.top].x][p.maze[p.top].y]=0;
				p.top--;
			}	
	}
}
int main()
{
	path(1,1,M,N);
	return 0;
}