输出迷宫的最短路径

谢坡坡

1. #include<stdio.h>  
   
2. #define M 8   //行数  
   
3. #define N 8     //列数  
   
4. #define MaxSize    100     //栈最多元素个数  
   
5. int mg[M+2][N+2]={      //一个迷宫，其四周要加上均为1的外框  
   
6.                     {1,1,1,1,1,1,1,1,1,1},  
   
7.                     {1,0,0,0,0,0,0,0,0,1},  
   
8.                     {1,0,0,1,1,0,1,1,0,1},  
   
9.                     {1,0,0,1,0,0,1,0,0,1},  
   
10.                     {1,0,1,1,1,0,1,1,0,1},  
    
11.                     {1,0,0,1,0,0,1,0,0,1},  
    
12.                     {1,0,0,1,1,0,1,0,0,1},  
    
13.                     {1,0,1,0,0,0,0,1,0,1},  
    
14.                     {1,0,0,0,0,1,0,0,0,1},  
    
15.                     {1,1,1,1,1,1,1,1,1,1}  
    
16. };  
    
17. struct migong{  
    
18.     int i;      //路径横坐标  
    
19.     int j;      //路径纵坐标  
    
20.     int di;     //方向  
    
21. }Stack[MaxSize],Path[MaxSize];      //定义栈和存放最短路径的数组  
    
22. int top=-1;     //栈顶指针  
    
23. int count=1;    //路径数计数  
    
24. int minlen=MaxSize;     //最短路径长度  
    
25. void mgpath()
    
26. {      //路径为:(1,1)->(M,N)  
    
27.     int i,j,di,find,k;  
    
28.     top++;
    
29.         Stack[top].i=1;
    
30.         Stack[top].j=1;
    
31.         Stack[top].di=-1;  //第一个点入栈
    
32.     mg[1][1]=-1;        //初始结点进栈  
    
33. 
    
34.     while(top>-1)
    
35.         {      //栈不空时循环  
    
36.         i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;  
    
37.         if(i==M && j==N)
    
38.                 {       //找到了出口，输出路径  
    
39.             printf("M:  ",count++);  
    
40.             for(k=0;k<=top;k++)
    
41.                         {  
    
42.                 printf("(%d,%d)  ",Stack[k].i,Stack[k].j);  
    
43.                 if((k+1)%5==0)      //输出时每5个结点换一行  
    
44.                     printf("\n\t");  
    
45.             }  
    
46.             printf("\n");  
    
47.             if(top+1<minlen)
    
48.                         {       //比较输出最短路径  
    
49.                 for(k=0;k<=top;k++)  
    
50.                     Path[k]=Stack[k];  
    
51.                 minlen=top+1;  
    
52.             }  
    
53.             mg[Stack[top].i][Stack[top].j]=0;   //让该位置变为其他路径的可走结点  
    
54.             top--;  
    
55.             i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;  
    
56.         }  
    
57.         find=0;  
    
58.         while(di<4 && find==0)
    
59.                 {     //找下一个可走结点  
    
60.             di++;  
    
61.             switch(di)
    
62.                         {  
    
63.                 case 0:i=Stack[top].i-1;j=Stack[top].j;break;   //上面  
    
64.                 case 1:i=Stack[top].i;j=Stack[top].j+1;break;   //右边  
    
65.                 case 2:i=Stack[top].i+1;j=Stack[top].j;break;   //下面  
    
66.                 case 3:i=Stack[top].i;j=Stack[top].j-1;break;   //左边  
    
67.             }  
    
68.             if(mg[i][j]==0)  
    
69.                 find=1;  
    
70.         }  
    
71.         if(find == 1)
    
72.                 {      //找到了下一个可走结点  
    
73.             Stack[top].di=di;   //修改原栈顶元素的di值  
    
74.             top++;      //下一个可走结点进栈  
    
75.             Stack[top].i=i;  
    
76.             Stack[top].j=j;  
    
77.             Stack[top].di=-1;  
    
78.             mg[i][j]=-1;        //避免重复走到该结点  
    
79.         }
    
80.                 else
    
81.                 {  
    
82.             mg[Stack[top].i][Stack[top].j]=0;   //让该位置变为其他路径的可走结点  
    
83.             top--;  
    
84.         }  
    
85.     }  
    
86.     printf("最短路径如下:\n");  
    
87.     printf("长度:  %d\n",minlen);  
    
88.     printf("路径:  ");  
    
89.     for(k=0;k<minlen;k++)
    
90.         {  
    
91.         printf("(%d,%d)  ",Path[k].i,Path[k].j);  
    
92.         if((k+1)%5==0)      //输出时每5个结点换一行  
    
93.             printf("\n\t");  
    
94.     }  
    
95.     printf("\n");  
    
96. }  
    
97. int main(){  
    
98.     printf("迷宫所有路径如下:\n");  
    
99.     mgpath();  
    
100.     return 0;  
     
101. }

复制代码

loewe

楼主厉害了，学习一下