文章目录
- 一、问题的描述
- 二、系统功能设计
- 三、各个代码部分
- 四、整体代码及其运行
- 五、总结
前言
迷宫求解–C语言
一、问题描述
在一个迷宫中，需要我们找到出去的道路，并且得到的路经是最短的。
迷宫设置如下：迷宫使用标记（0，1，2，3分别代表迷宫的墙壁，通道，入口和出口）
从开始点出发，每个点采取四领域方法，按照上、下、左、右四个方向的顺序搜索下一个相邻的点，有路则进，无路则退，并从下一个方向继续搜索。
二、系统功能设计
需要功能设计的功能有：
- 1、实现迷宫地图
- 2、求出最短路径
- 3、在迷宫中显示最短路径
三、各个代码部分
1、实现迷宫地图
1、主要以二维数组的方式来显示和存储
#include <stdio.h>
#include <stdlib.h>
int p,q,m,n,min=888; //设置行数m 与列数 n (p,q)为终点的坐标
int total = 0; //路径总数
int book[51][51]; //标记数组 用于判断下个坐标是否走过 走过则标记为1
int a[51][51]; // 1表示空地 0表示障碍物
int path1[51],path2[51];//保存路径的x，y坐标2、在二维数组中输入迷宫，0代表障碍，1代表可通路。并且输入起点和终点的坐标。
//创建迷宫
void createload()
{
int st,ed;
int i,j;
printf("-------------------开始创建迷宫-------------------\n");
printf("请分别输入迷宫的行数和列数：");
scanf("%d %d", &m, &n);
printf("请输入迷宫，可走的路径设置为1 障碍物设置为0：\n");
for (i=0; i <m; i++)
for (j =0; j <n; j++)
scanf("%d", &a[i][j]);
printf("请输入起点坐标：\n");
scanf("%d %d", &st, &ed);
book[st][ed] = 1;
printf("请输入终点坐标：\n");
scanf("%d %d", &p, &q);
printf("-------------------创建迷宫成功！-------------------\n");
printf("最短路径如下：\n");
printf("(%d,%d)",st,ed);
dfs(st, ed, 0);
printf("\n最短路径为%d\n",min);
a[st][ed] = 2;
a[p][q] = 3;
}效果如下：
2、求出最短路径
1、搜索方法有两种，一是深度优先搜索，二是广度优先搜索。
本系统使用的为深度优先搜索dfs
//深度优先搜素
void dfs(int x, int y, int step) {
int i;
if (x == p&& y == q)
{
total++;
if (step < min){ //如果step比min小，就修改min的值
min = step;
for(i = 0; i < step; i++){
printf("(%d,%d)",path1[i],path2[i]); //打印一维路径
a[path1[i]][path2[i]] = 5;
}
}
return; //如果到达了终点就回溯
}else {
if ( y + 1 <= n && a[x][y+1] == 1 && book[x][y+1]==0) //判断边界以及该坐标是否被标记和是否是空地
{
book[x][y+1] = 1; // 递去阶段：当走到当前位置，标记已走过
path1[step] = x; //缓存x
path2[step] = y+1; //缓存y
dfs(x , y+1, step + 1); // 进行该位置的深度优先搜索
book[x][y+1] = 0; // 回溯阶段： 取消该标记，并按顺序继续移动
}
if ( x + 1 <= m && a[x+1][y] == 1 && book[x+1][y ] == 0)
{
book[x+1][y] = 1;
path1[step] = x+1; //缓存x
path2[step] = y; //缓存y
dfs(x+1, y , step + 1);
book[x+1][y] = 0;
}
if (0 < y -1 && a[x][y -1] == 1 && book[x][y - 1] == 0)
{
book[x][y -1] = 1;
path1[step] = x; //缓存x
path2[step] = y-1; //缓存y
dfs(x, y - 1, step + 1);
book[x][y - 1] = 0;
}
if (0 < x -1 && a[x - 1][y] == 1 && book[x -1][y] == 0)
{
book[x - 1][y] = 1;
path1[step] = x-1; //缓存x
path2[step] = y; //缓存y
dfs(x -1, y, step + 1);
book[x -1][y] = 0;
}
return; //当无路可走时 回溯上一个位置；
}
}3、在迷宫中显示最短路经
//显示迷宫路径
void printload()
{
int i,j;
printf("最短路径显示如下：\n");
for (i=0; i <m; i++){
for (j =0; j <n; j++){
printf("%d ", a[i][j]);
}
printf("\n");
}
}
四、整体代码及其整体运行
1、所有代码如下：建议将子函数放在另一个文件里，与主函数区分开。
#include <stdio.h>
#include <stdlib.h>
int p,q,m,n,min=888; //设置行数m 与列数 n (p,q)为终点的坐标
int total = 0; //路径总数
int book[51][51]; //标记数组 用于判断下个坐标是否走过 走过则标记为1
int a[51][51]; // 1表示空地 0表示障碍物
int path1[51],path2[51];//保存路径的x，y坐标
void createload();//创建迷宫
void dfs(int x, int y, int step);//深度优先搜索迷宫
void printload();//显示迷宫最短路径
//创建迷宫
void createload()
{
int st,ed;
int i,j;
printf("-------------------开始创建迷宫-------------------\n");
printf("请分别输入迷宫的行数和列数：");
scanf("%d %d", &m, &n);
printf("请输入迷宫，可走的路径设置为1 障碍物设置为0：\n");
for (i=0; i <m; i++)
for (j =0; j <n; j++)
scanf("%d", &a[i][j]);
printf("请输入起点坐标：\n");
scanf("%d %d", &st, &ed);
book[st][ed] = 1;
printf("请输入终点坐标：\n");
scanf("%d %d", &p, &q);
printf("-------------------创建迷宫成功！-------------------\n");
printf("最短路径如下：\n");
printf("(%d,%d)",st,ed);
dfs(st, ed, 0);
printf("\n最短路径为%d\n",min);
a[st][ed] = 2;
a[p][q] = 3;
}
//深度优先搜素
void dfs(int x, int y, int step) {
int i;
if (x == p&& y == q)
{
total++;
if (step < min){ //如果step比min小，就修改min的值
min = step;
for(i = 0; i < step; i++){
printf("(%d,%d)",path1[i],path2[i]); //打印一维路径
a[path1[i]][path2[i]] = 5;
}
}
return; //如果到达了终点就回溯
}else {
if ( y + 1 <= n && a[x][y+1] == 1 && book[x][y+1]==0) //判断边界以及该坐标是否被标记和是否是空地
{
book[x][y+1] = 1; // 递去阶段：当走到当前位置，标记已走过
path1[step] = x; //缓存x
path2[step] = y+1; //缓存y
dfs(x , y+1, step + 1); // 进行该位置的深度优先搜索
book[x][y+1] = 0; // 回溯阶段： 取消该标记，并按顺序继续移动
}
if ( x + 1 <= m && a[x+1][y] == 1 && book[x+1][y ] == 0)
{
book[x+1][y] = 1;
path1[step] = x+1; //缓存x
path2[step] = y; //缓存y
dfs(x+1, y , step + 1);
book[x+1][y] = 0;
}
if (0 < y -1 && a[x][y -1] == 1 && book[x][y - 1] == 0)
{
book[x][y -1] = 1;
path1[step] = x; //缓存x
path2[step] = y-1; //缓存y
dfs(x, y - 1, step + 1);
book[x][y - 1] = 0;
}
if (0 < x -1 && a[x - 1][y] == 1 && book[x -1][y] == 0)
{
book[x - 1][y] = 1;
path1[step] = x-1; //缓存x
path2[step] = y; //缓存y
dfs(x -1, y, step + 1);
book[x -1][y] = 0;
}
return; //当无路可走时 回溯上一个位置；
}
}
//显示迷宫路径
void printload()
{
int i,j;
printf("最短路径显示如下：\n");
for (i=0; i <m; i++){
for (j =0; j <n; j++){
printf("%d ", a[i][j]);
}
printf("\n");
}
}
int main()
{
createload();
printload();
return 0;
}
2、整体运行结果如下：
五、总结
太多了不会？跟着我的代码敲，熟能生巧，一个一个模块去做，分治法大事化小。看着代码自己打一遍，能运行就是成功。
文章出处登录后可见！
已经登录？立即刷新
