如何使用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。

相关文章

C语言中联合体union的使用

C语言中联合体union的使用

本文编辑整理自： http://bbs.chinaunix.net/forum.php?mod=viewthread&tid=179471 一、前言 “联合体”(union）与“结构体”(struct)有一些相似之处。但两者有本质上的不同。在结构体中,各成员有各自的内存空间, 一个结构变量的总长度是各成员长度之和。而在“联合”中,各成员共享一段内存空间, 一个联合变量
阅读更多...
C++对象布局及多态实现探索之内存布局（整理的很多链接）

C++对象布局及多态实现探索之内存布局（整理的很多链接）

本文通过观察对象的内存布局，跟踪函数调用的汇编代码。分析了C++对象内存的布局情况，虚函数的执行方式，以及虚继承，等等 文章链接：http://dev.yesky.com/254/2191254.shtml      论C/C++函数间动态内存的传递 (2005-07-30)   当你涉及到C/C++的核心编程的时候，你会无止境地与内存管理打交道。 文章链接：http://dev.yesky
阅读更多...
Tolua使用笔记（上）

Tolua使用笔记（上）

目录   1.准备工作 2.运行例子 01.HelloWorld：在C#中，创建和销毁Lua虚拟机 和 简单调用。 02.ScriptsFromFile：在C#中，对一个lua文件的执行调用 03.CallLuaFunction：在C#中，对lua函数的操作 04.AccessingLuaVariables：在C#中，对lua变量的操作 05.LuaCoroutine：在Lua中，
阅读更多...
一份LLM资源清单围观技术大佬的日常；手把手教你在美国搭建「百万卡」AI数据中心；为啥大模型做不好简单的数学计算？ | ShowMeAI日报

一份LLM资源清单围观技术大佬的日常；手把手教你在美国搭建「百万卡」AI数据中心；为啥大模型做不好简单的数学计算？ | ShowMeAI日报

👀日报&周刊合集 | 🎡ShowMeAI官网 | 🧡 点赞关注评论拜托啦！ 1. 为啥大模型做不好简单的数学计算？从大模型高考数学成绩不及格说起 司南评测体系 OpenCompass 选取 7 个大模型 (6 个开源模型+ GPT-4o)，组织参与了 2024 年高考「新课标I卷」的语文、数学、英语考试，然后由经验丰富的判卷老师评判得分。 结果如上图所
阅读更多...
Vim使用基础篇

Vim使用基础篇

本文内容大部分来自 vimtutor，自带的教程的总结。在终端输入vimtutor 即可进入教程。 先总结一下，然后再分别介绍正常模式，插入模式，和可视模式三种模式下的命令。 目录 看完以后的汇总 1.正常模式（Normal模式） 1.移动光标 2.删除 3.【:】输入符 4.撤销 5.替换 6.重复命令【. ; ,】 7.复制粘贴 8.缩进 2.插入模式 INSERT
阅读更多...
Lipowerline5.0 雷达电力应用软件下载使用

Lipowerline5.0 雷达电力应用软件下载使用

1.配网数据处理分析 针对配网线路点云数据，优化了分类算法，支持杆塔、导线、交跨线、建筑物、地面点和其他线路的自动分类；一键生成危险点报告和交跨报告；还能生成点云数据采集航线和自主巡检航线。 获取软件安装包联系邮箱:2895356150@qq.com，资源源于网络，本介绍用于学习使用，如有侵权请您联系删除！ 2.新增快速版，简洁易上手 支持快速版和专业版切换使用，快速版界面简洁，保留主
阅读更多...
如何免费的去使用connectedpapers？

如何免费的去使用connectedpapers？

免费使用connectedpapers 1. 打开谷歌浏览器2. 按住ctrl+shift+N,进入无痕模式3. 不需要登录（也就是访客模式）4. 两次用完，关闭无痕模式（继续重复步骤 2 - 4） 1. 打开谷歌浏览器 2. 按住ctrl+shift+N,进入无痕模式 输入网址：https://www.connectedpapers.com/ 3. 不需要登录（也就是
阅读更多...
大语言模型（LLMs）能够进行推理和规划吗？

大语言模型（LLMs）能够进行推理和规划吗？

大语言模型（LLMs），基本上是经过强化训练的 n-gram 模型，它们在网络规模的语言语料库（实际上，可以说是我们文明的知识库）上进行了训练，展现出了一种超乎预期的语言行为，引发了我们的广泛关注。从训练和操作的角度来看，LLMs 可以被认为是一种巨大的、非真实的记忆库，相当于为我们所有人提供了一个外部的系统 1（见图 1）。然而，它们表面上的多功能性让许多研究者好奇，这些模型是否也能在通常需要系
阅读更多...
通过SSH隧道实现通过远程服务器上外网

通过SSH隧道实现通过远程服务器上外网

搭建隧道 autossh -M 0 -f -D 1080 -C -N user1@remotehost##验证隧道是否生效，查看1080端口是否启动netstat -tuln | grep 1080## 测试ssh 隧道是否生效curl -x socks5h://127.0.0.1:1080 -I http://www.github.com 将autossh 设置为服务，隧道开机启动
阅读更多...
时序预测 | MATLAB实现LSTM时间序列未来多步预测-递归预测

时序预测 | MATLAB实现LSTM时间序列未来多步预测-递归预测

时序预测 | MATLAB实现LSTM时间序列未来多步预测-递归预测 目录 时序预测 | MATLAB实现LSTM时间序列未来多步预测-递归预测基本介绍程序设计参考资料 基本介绍 MATLAB实现LSTM时间序列未来多步预测-递归预测。LSTM是一种含有LSTM区块（blocks）或其他的一种类神经网络，文献或其他资料中LSTM区块可能被描述成智能网络单元，因为
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2