#include<stdio.h>
#define m 10
#define n 15
#define NUM m*n
typedef struct
{
   int x,y;/*x,y为到达点的坐标*/
   int pre;/*pre为（x,y)的前驱点在数组sq中的下标*/
}sqtype;
int maze[m+1][n+1];
typedef struct
{
   int dx;
   int dy;
}moved;

void shortpath(int maze[m][n],moved move[8])
{ 
   sqtype sq[NUM];
   int front,rear;
   int x,y,i,j,v;
   front=rear=0;
   sq[0].x=1;
   sq[0].y=1;
   sq[0].pre=-1;/*选（1,1）点为入口点入队*/
   maze[1][1]=-1;/*表示该点搜索过了，所以置成-1。该点是入口点，原值为0*/
   while(front<=rear)/*队列不空*/
   {
        x=sq[front].x;
        y=sq[front].y;
        for(v=0;v<8;v++)/*循环扫描每个方向，共八个方向*/
  {
             i=x+move[v].dx;
    j=x+move[v].dy;/*选择一个前进的方向（i,j)*/
             if(maze[i][j]==0)/*如果该方向可走*/
               {
                  rear++;/*入队*/
                  sq[rear].x=i;
                  sq[rear].y=j;
                  sq[rear].pre=front;
                  maze[i][j]=-1;/*将其赋值为-1，以免重复搜索*/
                }
              if(i==m && j==n)/*找到了出口*/
     {
      printpath(sq,rear);/*打印迷宫*/
                   restore(maze);/*回复迷宫，使数组maze中的-1全变成0*/
                   return 1;
     }
  }
          front++;/*当前点搜索完，取下一个点搜索*/
   }
          return 0;
}

void printpath(sqtype sq[],int rear)/*打印迷宫*/
{
   int i;
   i=rear;
   do
   {
       printf("(%d,%d)?",sq[i].x,sq[i].y);
       i=sq[i].pre;/*回溯*/
   }
    while(i!=-1);
}