#include <stdio.h>
#include<stdlib.h>
struct stack_node
{
	int x;                    /*坐標*/
	int y;
	struct stack_node *next;     /*指向下一坐標*/
};
typedef struct stack_node stack_list;
typedef stack_list *link;
link path=NULL;

link push(link stack,int x,int y )        /*棧數據的輸入*/
{
	link new_node;
	new_node=(link)malloc(sizeof(stack_list));
	if(!new_node)
	{
		printf("內存分配失敗!\n");
		return NULL;
	}
	new_node->x=x;
	new_node->y=y;
	new_node->next=stack;
	stack=new_node;
	return stack;
}
link pop(link &stack,int *x,int *y)       /*棧數據的取出*/
{
	link top;
	if(stack!=NULL)
	{  
		top=stack;
		if(stack!=NULL)
		    stack=stack->next;
		*x=stack->x;
		*y=stack->y;
		free(top);
		return stack;
	}
	else
		*x=-1;
	return NULL;
}
void main()
{
	int maze[5][5];
	int i,j;
	printf("shurumigong maze:");
	for(i=0;i<=4;i++)
	{for(j=0;j<=4;j++)
		 scanf("%d",&maze[i][j]);
	}
	int x=4; /*入坐標*/
	int y=4;
	printf("the original maze is:\n");
	for(i=0;i<=4;i++)
	{
		for(j=0;j<=4;j++)			
		{	
			printf("%d ",maze[i][j]);
		}
		printf("\n");
	}
	while(x!=0||y!=0)
	{    
		maze[x][y]=2;               /*標示走過的路*/
		if((x-1)>=0&&maze[x-1][y]<=0)        /*往上走*/
		{
			x=x-1;
			path=push(path,x,y);
		}
		else
			if((x+1)<=4&&maze[x+1][y]<=0)           /*往下走*/
			{
				x=x+1;
				path=push(path,x,y);
			}
			else
				if((y-1)>=0&&maze[x][y-1]<=0)          /*往左走*/
				{
					y=y-1;
					path=push(path,x,y);
				}
				else
					if((y+1)<=4&&maze[x][y+1]<=0)          /*往右走*/
					{
						y=y+1;
						path=push(path,x,y);
					}
					else
					{
						maze[x][y]=3;                /*用3表示回朔的路*/
						path=pop(path,&x,&y);
					}
	}
	maze[x][y]=2;               /*標識最后一點*/
	printf("路徑如下圖:\n");
	for(i=0;i<=4;i++)
	{
		for(j=0;j<=4;j++)
			if(maze[i][j]==2)
				printf("(%d %d) ",i,j);
	}
}