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

winston · 发表于 2012-5-23 21:36:07

本文给出一个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，表示没有一条路径可走，否则打印出
口距入口的距离。
全部的代码见下：

#include <stdlib.h>
#include <stdio.h>
#include <memory.h>
#include <queue>
using namespace std;
#define MAX_WIDTH 30
#define MAX_HEIGHT 30
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;
MATRIX g_matrix= //初始化为一个迷宫，程序也能从文件中读入迷宫数据
{
{
{-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},
},
7,7, //7行，7列，包括4堵墙
{1,1}, //入口坐标
{5,5} //出口坐标
};
static STEP s_shift[]=
{
{1,0,0}, //向右走， x++, y 不变
{0,1,0}, //向下走, x 不变, y++
{-1,0,0}, //向左走, x--, y不变
{0,-1,0} //向上走, x 不变, y--
};
void print_Matrix(MATRIX* pMatrix) //打印迷宫数据，迷宫数据包含4堵墙
{
int i,j;
for (i=0;i<pMatrix->height;i++)
{
for (j=0;j<pMatrix->width;j++)
{
if (j!=0)
printf(" ");
printf("%d",pMatrix->data[i][j]);
}
printf("\n");
}
}
int search_min_distance(int matric[MAX_WIDTH+2][MAX_WIDTH+2], STEP entrance, STEP exit)
{
deque<STEP> my_queue;
STEP t1,t2;
int i;
t1=entrance;
t1.distance=0;
my_queue.push_back(t1);
while ( !my_queue.empty() )
{
t1=my_queue.front();
my_queue.pop_front();
t2.distance =t1.distance +1;
for (i=0;i<4;i++)
{
t2.x=t1.x + s_shift[i].x;
t2.y=t1.y + s_shift[i].y;
if ( (t2.x!=entrance.x || t2.y !=entrance.y) && matric[t2.x][t2.y] != -1 )
{
if ( matric[t2.x][t2.y]==0 || matric[t2.x][t2.y]> t2.distance)
{
matric[t2.x][t2.y]=t2.distance;
my_queue.push_back(t2);
}
}
}
}
return matric[exit.x][exit.y];
}
int readMatrix(char *file)
{
char line[1024];
FILE *fp=NULL;
int i,j,x,y;
fp=fopen(file,"rt");
if (fp==NULL)
{
printf("Can not open file %s\n",file);
return 0;
}
memset(&(g_matrix),0,sizeof(g_matrix));
fgets(line,sizeof(line)-1,fp);
sscanf(line,"%d %d",&x,&y); //读入迷宫的行数和列数
if ( x>MAX_WIDTH || y>MAX_HEIGHT)
{
printf("The Matrix is too large\n");
fclose(fp);
return 0;
}
g_matrix.width=x+2; //在4条边增加4堵墙，故宽和高增加2
g_matrix.height=y+2;
for (j=0;j<g_matrix.width;j++)
{
g_matrix.data[0][j]=-1; //第一行为墙
g_matrix.data[g_matrix.height-1][j]=-1; //最后一行为墙
}
for (i=0;i<g_matrix.height;i++)
{
g_matrix.data[i][0]=-1; //最左边的列为墙
g_matrix.data[i][g_matrix.width-1]=-1; //最右边的列为墙
}
for (i=1;i<g_matrix.height-1;i++)
{
char *p;
fgets(line,sizeof(line)-1,fp);
j=1;
p=line;
while (1)
{
while ( *p==' ' || *p== 9 || *p== ',' )//跳过空格和逗号
p++;
if ( *p>='0' && *p<='9'|| *p == '-')
{
sscanf(p,"%d",&(g_matrix.data[i][j])); //读入地i行j列的数据
while ( *p>='0' && *p<='9'|| *p== '-' )
p++; //数据已经读入，跳过当前的数字
j++;
}
if (j>=g_matrix.width-2)
break;
}
}
fgets(line,sizeof(line)-1,fp);
//读入入口的行坐标和列坐标，和出口的行坐标，列坐标
sscanf(line,"%d %d %d %d",&(g_matrix.entrance.x),&(g_matrix.exit.y),&(g_matrix.exit.x),&(g_matrix.exit.y));
fclose(fp); fp=NULL;
g_matrix.entrance.x++; //增加了一列是墙，故入口横坐标+1
g_matrix.entrance.y++; //增加了一行是墙，故入口纵坐标+1
g_matrix.exit.x++; //增加了一列是墙，故入口横坐标+1
g_matrix.exit.y++; //增加了一列是墙，故入口纵坐标+1
return 1;
}
int main()
{
int distance;
if ( !readMatrix("matrix.txt") ) //不使用初始化的数据，从文件中读入迷宫数据
{
return 0; //读取失败，直接跳出
}
printf("The original matrix is\n");
print_Matrix(&g_matrix);
distance= search_min_distance(g_matrix.data,g_matrix.entrance,g_matrix.exit);
printf("The new matrix is\n");
print_Matrix(&g_matrix);
printf("\nThe distance is %d\n",distance);
return 0;
}

复制代码

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

		自动登录	找回密码
密码			用户注册