#include<stdio.h>
#define m 5
#define n 5
#define MAX 400
struct node{
		int x,y;//方格點坐標
		int pre; //前趨點指示
};
int maze[m][n];
/*={0,0,0,0,0,
		        0,0,0,0,0,
			    0,0,0,0,0,
		   	    0,0,0,0,0,
		        0,0,0,0,0}; //迷宮數(shù)組*/
int front,rear;
struct node sq[MAX];//既是紀錄搜索路經(jīng)的數(shù)組又是隊結(jié)構(gòu)（非循環(huán)隊）
int zx[8],zy[8];


void printpace(int rear)       //打印迷宮路徑           
{
    int i;
	i=rear;
	do
	{
		printf("(%d, %d)<--", sq[i].x, sq[i].y);
		i=sq[i].pre;
	}while(i!=0); 
}

void mazep()                  //搜索迷宮路徑
{
	int i, j, x, y, v, front, rear, find;
	sq[1].x=1; sq[1].y=1; sq[1].pre=0;   //從（1， 1）搜索
	find=0;
	front=1; rear=1; maze[1][1]=-1;
	while(front<=rear&&!find)
    {
		x=sq[front].x; y=sq[front].y;
		for(v=1; v<=8; v++)         //對八個周圍方向進行循環(huán)掃描
        {
			i=x+zx[v]; j=y+zy[v];  //任選一個方向走
			if(maze[i][j]==0)            //如果該方向可走
			{
				rear++;          //進隊
				sq[rear].x=i;
				sq[rear].y=j;
				sq[rear].pre=front;
				maze[i][j]=-1;       //為了避免從頭再搜索的賦值
			}
		    if(i==m && j==n)        //找到出口標志
            {
				printpace(rear);
				find=1;
			}
		}
	   front++;
	}
    if(!find)   printf("不存在走出迷宮的路徑！\n");
}

void main()
{
	int i, j;
	for(i=1; i<=m; i++)
		for(j=1; j<=n; j++)
		{
			printf("請您輸入第%d行第%d列的狀態(tài)數(shù): 0 或 1\n", i, j);
			scanf("%1d", &maze[i][j]);
		}
		
		          
    for(i=0; i<=m+1; i++)
    {
		maze[i][0]=1; maze[i][n+1]=1;
	}
	for(j=0; j<=n+1; j++)
	{
		maze[0][j]=1; maze[m+1][j]=1;
	}
    zx[1]=-1;zx[2]=-1;zx[3]=0;zx[4]=1;zx[5]=1;zx[6]=1; zx[7]=0; zx[8]=-1;
    zy[1]=0; zy[2]=1; zy[3]=1;zy[4]=1;zy[5]=0;zy[6]=-1;zy[7]=-1;zy[8]=-1;
	printf("走出迷宮的路徑如下(數(shù)字表示迷宮元素狀態(tài)的下標):\n");
	mazep();
}