迷宫问题

 1 #include<stdio.h>
 2 #include<string.h>
 3 struct note
 4 {
 5     int x,y,s;
 6 };
 7 int main()
 8 {
 9     struct note que[10010];
10     char a[110][110];
11     int book[110][110];
12     int next[4][2]={0,1,1,0,0,-1,-1,0};
13     int head,tail，T,i,j,k,n,m,sx,sy,ex,ey,tx,ty,flag;
14     
15     scanf("%d",&T);
16     while(T--)
17     {
18         scanf("%d%d",&n,&m);
19         getchar();//吃掉换行 
20         for(i=1;i<=n;i++){
21             for(j=1;j<=m;j++){
22                 scanf("%c",&a[i][j]);
23                 if(a[i][j]==‘S‘)
24                 {
25                     sx=i;
26                     sy=j;
27                     a[i][j]=‘-‘;//更改成可行路径 
28                 }
29                 if(a[i][j]==‘E‘)
30                 {
31                     ex=i;
32                     ey=j;
33                     a[i][j]=‘-‘;
34                 }
35             }
36             getchar();
37         }
38 
39         head=1;
40         tail=1;
41         que[tail].x=sx;
42         que[tail].y=sy;
43         que[tail].s=0;
44         tail++;
45         
46         memset(book,0,sizeof(book));//初始化 
47         book[sx][sy]=1;
48         flag=0;
49         while(head<tail)
50         {
51             for(k=0;k<=3;k++)
52             {
53                 tx=que[head].x+next[k][0];
54                 ty=que[head].y+next[k][1];
55                 if(tx<1 || tx>n ||ty<1 ||ty>m)
56                     continue;
57                 if(a[tx][ty]==‘-‘ && book[tx][ty]==0)
58                 {
59                     book[tx][ty]=1;
60                     que[tail].x=tx;
61                     que[tail].y=ty;
62                     que[tail].s=que[head].s+1;
63                     tail++;
64                 } 
65                  if(tx==ex && ty==ey)
66                  {
67                      flag=1;
68                      break;
69                  }
70             }
71             if(flag)
72                 break;
73             head++;
74         }
75         if(flag)
76         printf("%d\n",que[tail-1].s);
77         else
78         printf("-1\n");
79     }
80     return 0;
81 }