如何使用C语言实现简单迷宫(递归和非递归实现 含图例)

2024-04-30 10:18
文章标签 语言 简单 实现 使用 递归 图例 迷宫

本文主要是介绍如何使用C语言实现简单迷宫(递归和非递归实现 含图例)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.非递归实现

简单迷宫：只有一条通路的迷宫

思路：在找迷宫通路的时候，我们往往是在给定入口(入口合法且为通路)的情况下，沿着入口的某个方向走（此方向是通路）。现给定走迷宫的方向：上、左、右、下，即优先朝“上”走，如果“上”不通，朝“左”走；如果“左” 不通，朝“右”走；“右”再不通的话，朝“下”走。每次在当前步cur可以走通的情况下，先将cur保存起来，并将其标记成已走过的步，然后判断下一步next（优先朝“上”）是否可以走通。在next可以走通的情况下，继续上述过程，直到找到出口。    但这里有一个问题，当cur步的上下左右均走不通的时候我们该怎么办呢？--->此时表明cur步走错了，我们不应该再将其保存起来，因为此时的cur不是路径的一部分，并且还应该将其标记成走错的步，然后回退到上一步，继续朝其它方向（假设开始cur是从“上”回退的，那么此时cur可以向“左”走）寻找通路。  前边提到如果cur可以走通，我们便将其保存起来，然后走next步，这里我们可以用“栈”保存路径。找到一个可以走通的cur便让其入栈（保存起来），如果cur步走错了的话再让其出栈（不保存走错的cur步）。这样我们便充分利用了栈“后进先出”的特性。

现给定一个简单迷宫如下图所示（0表示不通，1表示可以走通）：

为了方便描述位置，我们用二维数组来表示其每个点坐标。

现给定入口坐标(3,1)：

1.先判断入口坐标是否合法（坐标是否在边界，值是否为1）

2.在入口合法的情况下，先让其入栈保存，并标记成已走步（现为了简便，将其标记成2）

 3.此时优先朝入口的上方寻找通路，如果next步可以走通，入栈保存next，并将其标记成已走步2

（ 如果上方不通，朝左走，如果next步可以走通，入栈保存next，并将其标记成已走步2

  如果左边不通，朝右走，如果next步可以走通，入栈保存next，并将其标记成已走步2

  如果右边不通，朝下走，如果next步可以走通，入栈保存next，并将其标记成已走步2）

 4.在每次入栈保存位置坐标之后，判断是否是出口，如果是出口，直接返回；如果不是，继续步骤3

具体寻找通路过程如下所示（上方的图形表示栈）：

                                         

 源代码如下：

//Stack.h:
#pragma once#define MAX_SIZE 100
#include <assert.h>
#include <stdio.h>typedef Position SDataType;
typedef struct Stack
{SDataType array[MAX_SIZE];int top;      //size
}Stack;// 初始化 
void StackInit(Stack *pStack)
{assert(pStack);pStack->top = 0;
}// 压栈 
void StackPush(Stack *pStack, SDataType data)
{assert(pStack);if (MAX_SIZE == pStack->top){printf("栈已满\n");return;}pStack->array[pStack->top] = data;pStack->top++;
}//判空 空返回1
int StackEmpty(Stack *pStack)
{assert(pStack);if (0 == pStack->top)return 1;return 0;
}// 出栈 
void StackPop(Stack *pStack)
{assert(pStack);if (StackEmpty(pStack)){printf("栈为空\n");return;}pStack->top--;
}// 返回栈顶元素 
SDataType StackTop(Stack *pStack)
{assert(pStack);return pStack->array[pStack->top - 1];
}// 返回数据个数 
int StackSize(Stack *pStack)
{assert(pStack);return pStack->top;
}

//Maze.h//简单迷宫（非递归）
#pragma oncetypedef struct Position   
{int _x;int _y;
}Position;#define MAX_ROW  4
#define MAX_COL  4typedef struct Maze
{int _map[MAX_ROW][MAX_COL];
}Maze;//Maze.c
#include <stdio.h>
#include <assert.h>
#include "Stack.h"//初始化迷宫
void InitMaze(Maze *m, int map[][MAX_COL])
{int i, j;if (NULL == m){return;}for (i = 0; i < MAX_ROW; i++){for (j = 0; j < MAX_COL; j++){m->_map[i][j] = map[i][j];}}
}//判断入口是否合法
int IsValidEntry(Maze *m, Position entry)
{assert(m);    //保证迷宫存在if (0 == entry._x || entry._x == MAX_ROW - 1 || 0 == entry._y || entry._y == MAX_COL - 1)   //在边界{return 1 == m->_map[entry._x][entry._y];     //如果存的是1，表示是通路；否则，不是通路}return 0;    //不在边界则一定不是合法入口
}//判断是否是通路
int IsPass(Maze *m, Position cur)
{   //cur一定在迷宫中if (1 == m->_map[cur._x][cur._y])  //若cur步存的是1，则表示是通路{return 1;}return 0;
}//判断是否是出口
int IsExit(Maze *m, Position cur, Position entry)
{if (cur._x == entry._x && cur._y == entry._y)  //如果cur等于entry(入口)，表明不是出口{return 0;}if (0 == cur._x || cur._x == MAX_ROW - 1 || 0 == cur._y || cur._y == MAX_COL - 1) //在cur不是入口的前提下，如果cur在边界，则表明是出口{return 1;}return 0;
}//entry表示迷宫的入口，栈s保存走过的路径
void PassMaze(Maze *m, Position entry, Stack *s)
{Position cur,next;//先判断入口是否合法，不合法直接退出if (!IsValidEntry(m, entry)){printf("非法的迷宫入口!\n");return;}StackPush(s,entry);    //入口合法，让其入栈while (!StackEmpty(s))    //栈不为空，表明有出口。若迷宫没有入口，则cur会一直出栈，直到空{cur = StackTop(s);  //取栈顶（前提：栈不为空）m->_map[cur._x][cur._y] = 2; //标记一下，代表此位置已经走过if (IsExit(m, cur,entry))     //检测cur是否是出口，若为出口，直接返回退出{return;}//上next = cur;next._x -= 1;if (IsPass(m, next)){StackPush(s, next);    //下一步可以走通，让其入栈，先保存起来continue;}//左next = cur;next._y -= 1;if (IsPass(m, next)){StackPush(s, next);   //下一步可以走通，让其入栈，先保存起来continue;}//右next = cur;next._y += 1;if (IsPass(m, next)){StackPush(s, next);    //下一步可以走通，让其入栈，先保存起来continue;}//下next = cur;next._x += 1;if (IsPass(m, next)){StackPush(s, next);     //下一步可以走通，让其入栈，先保存起来continue;}StackPop(s);     //上下左右均走不通，表明cur步走错了，让其出栈，不要出现在最终路径中m->_map[cur._x][cur._y] = 3;     //标记走错的步为3}}//打印迷宫
void PrintMaze(Maze *m, int map[][MAX_COL])
{int i, j;if (NULL == m){return;}for (i = 0; i < MAX_ROW; i++){for (j = 0; j < MAX_COL; j++){printf("%d ", m->_map[i][j]);}printf("\n");}
}//打印最终路径
void Print(Stack *s)
{Position top;while (StackSize(s) > 1){top = StackTop(s);StackPop(s);printf("(%d,%d) <- ", top);}top = StackTop(s);printf("(%d,%d)\n", top);
}void TestMaze()
{int map[MAX_ROW][MAX_COL] = { { 0, 0, 0, 0},{ 0, 1, 0, 0},{ 0, 1, 1, 1},{ 0, 1, 0, 0}};Stack s;Position entry;Maze m;InitMaze(&m,map);PrintMaze(&m, map);printf("\n");StackInit(&s);entry._x = 3;entry._y = 1;PassMaze(&m, entry, &s);PrintMaze(&m, map);printf("\n");Print(&s);}

最终打印出来的路径如下图所示：

 

2.递归实现

思路：在给定入口（入口合法且为通路）的情况下，我们可以把入口的下一步，比如入口上方（上方为通路）作为新的入口点继续走迷宫，直到走完整个迷宫。

源代码如下：

//MazeR.h
//简单迷宫（递归）
#pragma oncetypedef struct Position
{int _x;int _y;
}Position;#define MAX_ROW  4
#define MAX_COL  4typedef struct Maze
{int _map[MAX_ROW][MAX_COL];
}Maze;//MazeR.c
#include <stdio.h>
#include <assert.h>//初始化
void InitMaze(Maze *m, int map[][MAX_COL])
{int i, j;if (NULL == m){return;}for (i = 0; i < MAX_ROW; i++){for (j = 0; j < MAX_COL; j++){m->_map[i][j] = map[i][j];}}
}//判断入口是否合法
int IsValidEntry(Maze *m, Position entry)
{assert(m);    //保证迷宫存在if (0 == entry._x || entry._x == MAX_ROW - 1 || 0 == entry._y || entry._y == MAX_COL - 1)   //在边界{return 1 == m->_map[entry._x][entry._y];    //如果存的是1，表示是通路；否则，不是通路}return 0;     //不在边界则一定不是合法入口
}//判断是否是通路
int IsPass(Maze *m, Position cur)
{   //cur一定在迷宫中if (1 == m->_map[cur._x][cur._y])  //若cur步存的是1，则表示是通路{return 1;}return 0;
}//判断是否是出口
int IsExit(Maze *m, Position cur, Position entry)
{if (cur._x == entry._x && cur._y == entry._y)  //如果cur等于entry(入口)，表明不是出口{return 0;}if (0 == cur._x || cur._x == MAX_ROW - 1 || 0 == cur._y || cur._y == MAX_COL - 1) //在cur不是入口的前提下，如果cur在边界，则表明是出口{return 1;}return 0;
}int _PassMaze(Maze *m, Position entry, Position cur)
{Position next;if (IsPass(m, cur)){m->_map[cur._x][cur._y] = 2;    //标记一下，代表此位置已经走过if (IsExit(m, cur, entry))     //检测cur是否是出口，若为出口，直接返回退出{return 1;}//上next = cur;next._x -= 1;if (_PassMaze(m, entry, next))   //递归时，next为下一次的入口，继续走迷宫{return 1;}//左next = cur;next._y -= 1;if (_PassMaze(m, entry, next))    //递归时，next为下一次的入口，继续走迷宫{return 1;}//右next = cur;next._y += 1;if (_PassMaze(m, entry, next))     //递归时，next为下一次的入口，继续走迷宫{return 1;}//下next = cur;next._x += 1;if (_PassMaze(m, entry, next))      //递归时，next为下一次的入口，继续走迷宫{return 1;}m->_map[cur._x][cur._y] = 3;    //cur步走错了，标记成3}return 0;
}//entry表示入口，栈s保存走过的路径
void PassMaze(Maze *m, Position entry)
{//先判断入口是否合法，不合法直接退出if (!IsValidEntry(m, entry)){printf("非法的迷宫入口!\n");return;}_PassMaze(m, entry, entry);      //第一个entry表示入口，第二个entry表示当前入口}//打印迷宫
void PrintMaze(Maze *m, int map[][MAX_COL])
{int i, j;if (NULL == m){return;}for (i = 0; i < MAX_ROW; i++){for (j = 0; j < MAX_COL; j++){printf("%d ", m->_map[i][j]);}printf("\n");}
}void TestMaze()
{int map[MAX_ROW][MAX_COL] = { { 0, 0, 0, 0 },{ 0, 1, 0, 0 },{ 0, 1, 1, 1 },{ 0, 1, 0, 0 } };Position entry;Maze m;InitMaze(&m, map);PrintMaze(&m, map);printf("\n");entry._x = 3;entry._y = 1;PassMaze(&m, entry);PrintMaze(&m, map);printf("\n");}

 

这篇关于如何使用C语言实现简单迷宫(递归和非递归实现 含图例)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/948595。

相关文章

关于集合与数组转换实现方法

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》：本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方
阅读更多...
使用Python实现可恢复式多线程下载器

使用Python实现可恢复式多线程下载器

《使用Python实现可恢复式多线程下载器》在数字时代,大文件下载已成为日常操作,本文将手把手教你用Python打造专业级下载器,实现断点续传,多线程加速,速度限制等功能,感兴趣的小伙伴可以了解下... 目录一、智能续传：从崩溃边缘抢救进度二、多线程加速：榨干网络带宽三、速度控制：做网络的好邻居四、终端交互
阅读更多...
Python中注释使用方法举例详解

Python中注释使用方法举例详解

《Python中注释使用方法举例详解》在Python编程语言中注释是必不可少的一部分,它有助于提高代码的可读性和维护性,：本文主要介绍Python中注释使用方法的相关资料,需要的朋友可以参考下... 目录一、前言二、什么是注释？示例：三、单行注释语法：以 China编程# 开头，后面的内容为注释内容示例：示例：四
阅读更多...
java实现docker镜像上传到harbor仓库的方式

java实现docker镜像上传到harbor仓库的方式

《java实现docker镜像上传到harbor仓库的方式》：本文主要介绍java实现docker镜像上传到harbor仓库的方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录1. 前 言2. 编写工具类2.1 引入依赖包2.2 使用当前服务器的docker环境推送镜像2.2
阅读更多...
Go语言中nil判断的注意事项(最新推荐)

Go语言中nil判断的注意事项(最新推荐)

《Go语言中nil判断的注意事项(最新推荐)》本文给大家介绍Go语言中nil判断的注意事项,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1.接口变量的特殊行为2.nil的合法类型3.nil值的实用行为4.自定义类型与nil5.反射判断nil6.函数返回的
阅读更多...
C++20管道运算符的实现示例

C++20管道运算符的实现示例

《C++20管道运算符的实现示例》本文简要介绍C++20管道运算符的使用与实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录标准库的管道运算符使用自己实现类似的管道运算符我们不打算介绍太多，因为它实际属于c++20最为重要的
阅读更多...
Java easyExcel实现导入多sheet的Excel

Java easyExcel实现导入多sheet的Excel

《JavaeasyExcel实现导入多sheet的Excel》这篇文章主要为大家详细介绍了如何使用JavaeasyExcel实现导入多sheet的Excel,文中的示例代码讲解详细,感兴趣的小伙伴可... 目录1.官网2.Excel样式3.代码1.官网easyExcel官网2.Excel样式3.代码
阅读更多...
Go语言数据库编程GORM 的基本使用详解

Go语言数据库编程GORM 的基本使用详解

《Go语言数据库编程GORM的基本使用详解》GORM是Go语言流行的ORM框架,封装database/sql,支持自动迁移、关联、事务等,提供CRUD、条件查询、钩子函数、日志等功能,简化数据库操作... 目录一、安装与初始化1. 安装 GORM 及数据库驱动2. 建立数据库连接二、定义模型结构体三、自动迁
阅读更多...
python实现对数据公钥加密与私钥解密

python实现对数据公钥加密与私钥解密

《python实现对数据公钥加密与私钥解密》这篇文章主要为大家详细介绍了如何使用python实现对数据公钥加密与私钥解密,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录公钥私钥的生成使用公钥加密使用私钥解密公钥私钥的生成这一部分，使用python生成公钥与私钥，然后保存在两个文
阅读更多...
ModelMapper基本使用和常见场景示例详解

ModelMapper基本使用和常见场景示例详解

《ModelMapper基本使用和常见场景示例详解》ModelMapper是Java对象映射库,支持自动映射、自定义规则、集合转换及高级配置（如匹配策略、转换器）,可集成SpringBoot,减少样板... 目录1. 添加依赖2. 基本用法示例：简单对象映射3. 自定义映射规则4. 集合映射5. 高级配置匹
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2