一个求迷宫入口到出口最近距离的程序

winston

本文给出一个c/c++语言版的求迷宫最短路径的程序。程序的大部分使用标准c语言编写，包括输入和
输出。唯一用到C++库的地方是使用STL了中的deque。迷宫的宽和高，迷宫矩阵，迷宫的入口和出口从文
件读入。程序首先读入迷宫数据，然后求更新迷宫矩阵，并求出迷宫入口和出口的最短路径，并输出最
短路径长度。

1. 迷宫的表示。
迷宫用结构体MATRIX来表示
包括迷宫矩阵,迷宫的宽，迷宫的高，迷宫入口的坐标，迷宫出口的坐标。
结构体定义如下：
typedef struct _step
{
int x; //行坐标
int y; //列坐标
int distance; //距迷宫入口的距离
}STEP;
typedef struct _matrix
{
int data[MAX_WIDTH+2][MAX_WIDTH+2]; //迷宫数据，0：表示有路，1：表示墙
int width;  //矩阵（迷宫）的宽，包括最左和最有２堵墙
int height;  //矩阵（迷宫）的高，包括顶部和底部２堵墙
STEP entrance; //迷宫入口
STEP exit;  //迷宫出口
}MATRIX;

开始时，迷宫矩阵的每一个元素是0或-1，0表示可走，-1表示是墙，走不通。为了便于检查是否越界，
即坐标是否超过迷宫的范围。在迷宫的4个边增加了全-1数据，表示4堵墙。这样，在任何时候，都不
会越界。下面的数据表示1个5×5的迷宫，增加了4堵墙后，实际宽度和高度变为7，迷宫变成1个7×7
的矩阵。在搜索迷宫出口距入口的最近距离的过程中，需要修改矩阵相关元素的值。对所有和迷宫入
口相通的方格，其值被改为其距迷宫入口的最近距离。
-1, -1, -1, -1, -1, -1, -1,
-1,  0,  0,  0,  0,  0, -1,
-1, -1,  0, -1,  0, -1, -1,
-1,  0,  0, -1, -1, -1, -1,
-1,  0, -1,  0,  0,  0, -1,
-1,  0,  0,  0, -1,  0, -1,
-1, -1, -1, -1, -1, -1, -1,

2.算法
  迷宫的矩阵的每一方格可用三元组(x,y,d)来表示，x,y表示这个方格的坐标，d表示这个方格距入口
的距离.
  1.首先，将入口的坐标(x,y,0),放入双端队列my_queue。
  2. 接下来重复以下的过程，直到队列为空
    2.1.从队列头部取出一个三元组（x0,y0,d)
    2.2.从右，下，左，上四个方向搜索，看能否有非-1的格子
     如果可找到一个方格,其坐标为(x,y)，且这个方格不是入口点，则有3种情况
      case 1.
      新方格对应的矩阵元素是0，表明新的方格距迷宫入口的距离尚未标记。
   则将新方格对应的矩阵元素设置为d+1,同时将三元组(x,y,d+1)入队
      case 2：
      新方格的对应的矩阵元素的值>d+1,表明该新方格距迷宫入口的距离已经标记但不是最近的。
   则将新方格对应的矩阵元素设置为d+1,同时将三元组(x,y,d+1)入队  
   case 3:
    如果新的方格的对应的矩阵元素<= d+1，该位置距入口的距离已经标记，则不做处理
  3.检查出口对应的矩阵元素M[exit.x][exit.y]的值，如果为0，表示没有一条路径可走，否则打印出
    口距入口的距离。
全部的代码见下：

1. #include <stdlib.h>   
2. #include <stdio.h>   
3. #include <memory.h>   
4. #include <queue>
6. using namespace std;
8. #define MAX_WIDTH    30   
9. #define MAX_HEIGHT   30   
10.   
11. typedef struct _step  
12. {  
13.     int x;          //行坐标   
14.     int y;          //列坐标  
15.         int distance;   //距迷宫入口的距离       
16. }STEP;  
17.   
18. typedef struct _matrix  
19. {  
20.     int data[MAX_WIDTH+2][MAX_WIDTH+2]; //迷宫数据，0：表示有路，-1：表示墙   
21.     int width;              //矩阵（迷宫）的宽，包括最左和最有２堵墙   
22.     int height;             //矩阵（迷宫）的宽，包括顶部和底部２堵墙   
23.     STEP entrance;          //迷宫入口   
24.     STEP exit;              //迷宫出口   
25. }MATRIX;  
26.   
27. MATRIX g_matrix=                //初始化为一个迷宫，程序也能从文件中读入迷宫数据   
28. {  
29.     {  
30.        {-1, -1, -1, -1, -1, -1, -1},  
31.        {-1,  0,  0,  0,  0,  0, -1},  
32.        {-1, -1,  0, -1,  0, -1, -1},  
33.        {-1,  0,  0, -1, -1, -1, -1},  
34.        {-1,  0, -1,  0,  0,  0, -1},  
35.        {-1,  0,  0,  0, -1,  0, -1},  
36.        {-1, -1, -1, -1, -1, -1, -1},  
37.     },  
38.     7,7,                    //7行，7列，包括4堵墙   
39.     {1,1},                  //入口坐标   
40.     {5,5}                   //出口坐标   
41. };  
42.   
43.   
44. static STEP  s_shift[]=  
45. {  
46.     {1,0,0},      //向右走， x++, y 不变   
47.     {0,1,0},      //向下走,  x 不变, y++   
48.     {-1,0,0},     //向左走,  x--, y不变   
49.     {0,-1,0}      //向上走,  x 不变, y--   
50. };  
51.   
52. void print_Matrix(MATRIX* pMatrix)      //打印迷宫数据，迷宫数据包含4堵墙   
53. {  
54.     int i,j;  
55.     for (i=0;i<pMatrix->height;i++)  
56.     {  
57.         for (j=0;j<pMatrix->width;j++)  
58.         {  
59.             if (j!=0)  
60.                 printf(" ");  
61.             printf("%d",pMatrix->data[i][j]);  
62.         }  
63.         printf("\n");  
64.     }  
65. }  
66.   
67. int search_min_distance(int matric[MAX_WIDTH+2][MAX_WIDTH+2], STEP entrance, STEP exit)  
68. {  
69.     deque<STEP> my_queue;
70.         STEP t1,t2;
71.         int i;
72.         t1=entrance;
73.         t1.distance=0;
74.        
75.         my_queue.push_back(t1);
77.         while ( !my_queue.empty() )
78.         {
79.                 t1=my_queue.front();
80.                 my_queue.pop_front();
81.                
82.                
83.                 t2.distance =t1.distance +1;
84.                 for (i=0;i<4;i++)
85.                 {
86.                         t2.x=t1.x + s_shift[i].x;
87.                         t2.y=t1.y + s_shift[i].y;
88.                
89.                         if ( (t2.x!=entrance.x || t2.y !=entrance.y) && matric[t2.x][t2.y] != -1 )
90.                         {
91.                                 if  ( matric[t2.x][t2.y]==0 ||  matric[t2.x][t2.y]> t2.distance)
92.                                 {
93.                                         matric[t2.x][t2.y]=t2.distance;
94.                                         my_queue.push_back(t2);
95.                                 }
96.                         }
97.                 }
98.         }
99.        
100.         return  matric[exit.x][exit.y];
101.                
102. }  
103.   
104. int readMatrix(char *file)  
105. {  
106.     char line[1024];  
107.     FILE *fp=NULL;  
108.     int i,j,x,y;  
109.   
110.     fp=fopen(file,"rt");  
111.     if (fp==NULL)  
112.     {  
113.         printf("Can not open file %s\n",file);  
114.         return 0;  
115.     }  
116.   
117.     memset(&(g_matrix),0,sizeof(g_matrix));  
118.     fgets(line,sizeof(line)-1,fp);  
119.       
120.     sscanf(line,"%d %d",&x,&y);                 //读入迷宫的行数和列数   
121.     if ( x>MAX_WIDTH || y>MAX_HEIGHT)  
122.     {  
123.         printf("The Matrix is too large\n");  
124.         fclose(fp);  
125.         return 0;  
126.     }  
127.   
128.     g_matrix.width=x+2;                         //在4条边增加4堵墙，故宽和高增加2   
129.     g_matrix.height=y+2;  
130.       
131.     for (j=0;j<g_matrix.width;j++)  
132.     {  
133.         g_matrix.data[0][j]=-1;                  //第一行为墙   
134.         g_matrix.data[g_matrix.height-1][j]=-1;  //最后一行为墙   
135.     }  
136.   
137.     for (i=0;i<g_matrix.height;i++)        
138.     {  
139.         g_matrix.data[i][0]=-1;                  //最左边的列为墙   
140.         g_matrix.data[i][g_matrix.width-1]=-1;   //最右边的列为墙   
141.     }  
142.   
143.       
144.     for (i=1;i<g_matrix.height-1;i++)  
145.     {  
146.         char *p;  
147.         fgets(line,sizeof(line)-1,fp);  
148.         j=1;   
149.         p=line;  
150.         while (1)  
151.         {  
152.             while ( *p==' ' || *p== 9 || *p== ',' )//跳过空格和逗号
153.                 p++;  
154.   
155.             if ( *p>='0' && *p<='9'|| *p == '-')  
156.             {  
157.                 sscanf(p,"%d",&(g_matrix.data[i][j]));  //读入地i行j列的数据   
158.                 while ( *p>='0' && *p<='9'|| *p== '-' )  
159.                     p++;            //数据已经读入，跳过当前的数字   
160.                 j++;  
161.             }  
162.   
163.             if (j>=g_matrix.width-2)  
164.                 break;  
165.         }  
166.     }  
167.       
168.     fgets(line,sizeof(line)-1,fp);  
169.       
170.     //读入入口的行坐标和列坐标，和出口的行坐标，列坐标   
171.     sscanf(line,"%d %d %d %d",&(g_matrix.entrance.x),&(g_matrix.exit.y),&(g_matrix.exit.x),&(g_matrix.exit.y));  
172.     fclose(fp); fp=NULL;  
173.       
174.     g_matrix.entrance.x++;  //增加了一列是墙，故入口横坐标+1   
175.     g_matrix.entrance.y++;  //增加了一行是墙，故入口纵坐标+1   
176.     g_matrix.exit.x++;      //增加了一列是墙，故入口横坐标+1   
177.     g_matrix.exit.y++;      //增加了一列是墙，故入口纵坐标+1   
178.   
179.     return 1;  
180. }  
181.   
182. int main()  
183. {  
184.     int distance;
185.   
186.     if ( !readMatrix("matrix.txt") )  //不使用初始化的数据，从文件中读入迷宫数据   
187.     {  
188.         return 0;                     //读取失败，直接跳出      
189.     }  
190.   
191.     printf("The original matrix is\n");  
192.     print_Matrix(&g_matrix);  
194.         distance= search_min_distance(g_matrix.data,g_matrix.entrance,g_matrix.exit);
195.        
196.         printf("The new matrix is\n");  
197.         print_Matrix(&g_matrix);  
199.         printf("\nThe distance is %d\n",distance);
200.   
201.     return 0;  
202. }  

复制代码

作者：liangbch 发表于2012-5-23 16:28:21 原文链接