走迷宫问题

执行效果图：

寻找迷宫出路路径是递归算法中比较经典的问题。下面我将就迷宫的创建，迷宫出路的保存，以及某一迷宫出路的显示进行比较系统性的和大家讲解。

首先我们定义迷宫的大小和迷宫的难度系数（即空格数的比例，当难度系数为0.5时，空格数占0.7；当难度系数为1时，空格数占0.5）。

　　#define N 10 //迷宫大小N*N

　　#define M 0.8 //难度系数(0.5-1),默认为0.8

迷宫我们用一个二维数组maze[N][N]表示，其中0表示空格，1表示可走通路径，2表示围墙。

然后定义三个数组，其中a[]记录每种方案所需步数,b[]记录最短路径方案号，c[][3]保存所有合法方案图形(借助于稀疏矩阵的思想，其中c[][0]记录横坐标i的位置，c[][1]记录纵坐标j的位置，c[][2]记录的是可通路径)。

入口坐标为（1,1），出口坐标为（N-2，N-2）。然后定义静态全局标量t来记录临时路径号。定义结构体变量list来记录方案i存储在c[]中的起点和终点。

　　typedef struct list

　　{

　　　　int frist; //方案i存储在c[]中的起点

　　　　int last; //方案i存储在c[]中的终点

　　}list;

创建迷宫：通过随机生成空格坐标来实现迷宫数组的随机化。

 1 void creat_arr(int a[][N])   //创建迷宫数组
 2 {
 3     int i,j,x,y,tem,m=0,k[100];
 4     bool flag;
 5     srand(time(0));
 6     for(i=0;i<N;i++)
 7         for(j=0;j<N;j++)
 8             a[i][j]=2;
 9     for(i=0;i<(N-2)*(N-2)*(0.9-0.4*M);i++)  
10     {
11         flag=false;
12         x=rand()%(N-2)+1;
13         y=rand()%(N-2)+1;
14         tem=x*10+y;
15         for(j=0;j<m;j++)
16         {
17             if(tem==k[j])
18             {
19                 flag=true;
20                 break;
21             }
22         }
23         if(flag)
24         {
25             i--;
26         }
27         else
28         {
29             k[m++]=tem;
30             a[x][y]=0;
31         }
32     }    
33 }

保存方案：

 1 void save_arr(int a[][N])  //保存方案
 2 {
 3     int i,j;
 4     for(i=0;i<N;i++)
 5     {
 6         for(j=0;j<N;j++)
 7         {
 8             if(a[i][j]==1)
 9             {
10                 c[s][0]=i;
11                 c[s][1]=j;
12                 c[s++][2]=1;
13                 k++;
14             }
15         }
16     }
17 }

绘制图形：

 1 void print(int a[][N])  //绘制图形
 2 {
 3     int m,n;
 4     for(m=0;m<N;m++)
 5     {
 6         for(n=0;n<N;n++)
 7         {
 8             if(a[m][n]==2)
 9                 printf("█");
10             else if(a[m][n]==1)
11             {
12                 printf("╬");
13             }
14             else
15                 printf("∪");
16         }
17         printf("
");
18     }
19 }

绘制指定方案图形：

1 void print_show(int a[][N],int x,int y)  //绘制指定方案图形
2 {
3     int i;
4     for(i=x;i<y;i++)
5         a[c[i][0]][c[i][1]]=c[i][2];
6     print(a);
7     for(i=x;i<y;i++)      //显示结束后将图案还原成初始状态
8         a[c[i][0]][c[i][1]]=0;
9 }

核心代码：显示可通路径

 1 核心代码：显示可通路径
 2 
 3 void visit(int i,int j)  //显示路径
 4 {
 5     maze[i][j]=1;
 6     if(i==endI&&j==endJ)
 7     {
 8         k=0;
 9         printf("路径%d:",++t);
10         save_arr(maze);
11         li[t].frist=s-k;
12         li[t].last=s;
13         printf("共需移动%d步。
",k);
14         a[t-1]=k;
15     }
16     if(maze[i][j+1]==0)visit(i,j+1);
17     if(maze[i+1][j]==0)visit(i+1,j);
18     if(maze[i][j-1]==0)visit(i,j-1);
19     if(maze[i-1][j]==0)visit(i-1,j);
20     maze[i][j]=0;
21 }

全部执行代码：

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<time.h>
  4 
  5 #define N 10    //迷宫大小N*N
  6 #define M 0.8   //难度系数(0.5-1),默认为0.8
  7 static int t=0; //路径号
  8 
  9 int maze[N][N];  //迷宫数组
 10 
 11 int startI=1,startJ=1; // 入口
 12 int endI=N-2,endJ=N-2; // 出口
 13 int a[10000],b[10000],c[100000][3];  //a[]记录每种方案所需步数,b[]记录最短路径方案号，c[]保存所有合法方案图形
 14 int k=0,s=0;  //k步数,s储存所有方案时所用的标记值
 15 
 16 typedef struct list  
 17 { 
 18     int frist;   //方案i存储在c[]中的起点
 19     int last;    //方案i存储在c[]中的终点
 20 }list;
 21 
 22 list li[10000];
 23 
 24 void creat_arr(int a[][N])   //创建迷宫数组
 25 {
 26     int i,j,x,y,tem,m=0,k[100];
 27     bool flag;
 28     srand(time(0));
 29     for(i=0;i<N;i++)
 30         for(j=0;j<N;j++)
 31             a[i][j]=2;
 32     for(i=0;i<(N-2)*(N-2)*(0.9-0.4*M);i++)  //当难度系数为0.5时，空格数占0.7；当难度系数为1时，空格数占0.5
 33     {
 34         flag=false;
 35         x=rand()%(N-2)+1;
 36         y=rand()%(N-2)+1;
 37         tem=x*10+y;
 38         for(j=0;j<m;j++)
 39         {
 40             if(tem==k[j])
 41             {
 42                 flag=true;
 43                 break;
 44             }
 45         }
 46         if(flag)
 47         {
 48             i--;
 49         }
 50         else
 51         {
 52             k[m++]=tem;
 53             a[x][y]=0;
 54         }
 55     }    
 56 }
 57 
 58 void print(int a[][N])  //绘制图形
 59 {
 60     int m,n;
 61     for(m=0;m<N;m++)
 62     {
 63         printf("          ");
 64         for(n=0;n<N;n++)
 65         {
 66             if(a[m][n]==2)
 67                 printf("█");
 68             else if(a[m][n]==1)
 69             {
 70                 printf("╬");
 71             }
 72             else
 73                 printf("∪");
 74         }
 75         printf("
");
 76     }
 77 }
 78 
 79 void save_arr(int a[][N])  //保存方案
 80 {
 81     int i,j;
 82     for(i=0;i<N;i++)
 83     {
 84         for(j=0;j<N;j++)
 85         {
 86             if(a[i][j]==1)
 87             {
 88                 c[s][0]=i;
 89                 c[s][1]=j;
 90                 c[s++][2]=1;
 91                 k++;
 92             }
 93         }
 94     }
 95 }
 96 
 97 void print_show(int a[][N],int x,int y)  //绘制指定方案图形
 98 {
 99     int i;
100     for(i=x;i<y;i++)
101         a[c[i][0]][c[i][1]]=c[i][2];
102     print(a);
103     for(i=x;i<y;i++)      //显示结束后将图案还原成初始状态
104         a[c[i][0]][c[i][1]]=0;
105 }
106 
107 void visit(int i,int j)  //显示路径
108 {
109     maze[i][j]=1;
110     if(i==endI&&j==endJ)
111     {
112         k=0;
113         printf("路径%d:",++t);
114         save_arr(maze);
115         li[t].frist=s-k;
116         li[t].last=s;
117         printf("共需移动%d步。
",k);
118         a[t-1]=k;
119     }
120     if(maze[i][j+1]==0)visit(i,j+1);
121     if(maze[i+1][j]==0)visit(i+1,j);
122     if(maze[i][j-1]==0)visit(i,j-1);
123     if(maze[i-1][j]==0)visit(i-1,j);
124     maze[i][j]=0;
125 }
126 
127 int main(void)
128 {
129     int i,j,min,lu=0,mini=0,isok;
130     bool flag=true;
131     li[0].frist=0;
132     li[0].last=0;
133     printf("
显示路径:");
134     printf("

-----------------------------------------
");
135     while(t==0)
136     {
137         creat_arr(maze);
138         visit(startI,startJ);
139     }
140     printf("-----------------------------------------
");
141     printf("
显示迷宫:

");
142     print(maze);
143     printf("
共有%d种方案
",t);
144     min=a[0];
145     for(i=1;i<t;i++)
146     {
147         if(min>a[i])
148             min=a[i];
149     }
150     for(i=0;i<t;i++)
151     {
152         if(a[i]==min)
153             b[mini++]=i+1;
154     }
155     printf("最短需移动%d步。

",min);
156     if(mini==1)
157         printf("最短路径仅有%d条为:
",mini);
158     else
159         printf("最短路径有%d条，分别为:
",mini);
160     for(i=0;i<mini;i++)
161     {
162         printf("路径%d	",b[i]);
163         if((i+1)%5==0)
164             printf("
");
165     }
166     printf("

");
167     printf("是否要查看某一路径图案(1:是，0:否):");
168     scanf("%d",&isok);
169     printf("
");
170     if(isok==0)
171         return 0;
172     while(flag)
173     {
174         printf("请输入您要显示的路径图案(其中0为迷宫图):");
175         scanf("%d",&lu);
176         if(lu>t)
177         {
178             printf("您所输入的数字超出了要查看的最大路径号%d,请重新输入

",t);
179             continue;
180         }
181         printf("
");
182         print_show(maze,li[lu].frist,li[lu].last);
183         printf("
");
184         printf("是否继续查看(1:是，0:否):");
185         scanf("%d",&isok);
186         printf("
");
187         if(isok==0)
188             flag=false;
189     }
190     return 0;
191 }

View Code