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

相关文章

SpringBoot集成redisson实现延时队列教程

SpringBoot集成redisson实现延时队列教程

《SpringBoot集成redisson实现延时队列教程》文章介绍了使用Redisson实现延迟队列的完整步骤,包括依赖导入、Redis配置、工具类封装、业务枚举定义、执行器实现、Bean创建、消费... 目录1、先给项目导入Redisson依赖2、配置redis3、创建 RedissonConfig 配
阅读更多...
Python的Darts库实现时间序列预测

Python的Darts库实现时间序列预测

《Python的Darts库实现时间序列预测》Darts一个集统计、机器学习与深度学习模型于一体的Python时间序列预测库,本文主要介绍了Python的Darts库实现时间序列预测,感兴趣的可以了解... 目录目录一、什么是 Darts？二、安装与基本配置安装 Darts导入基础模块三、时间序列数据结构与
阅读更多...
Python使用FastAPI实现大文件分片上传与断点续传功能

Python使用FastAPI实现大文件分片上传与断点续传功能

《Python使用FastAPI实现大文件分片上传与断点续传功能》大文件直传常遇到超时、网络抖动失败、失败后只能重传的问题,分片上传+断点续传可以把大文件拆成若干小块逐个上传,并在中断后从已完成分片继... 目录一、接口设计二、服务端实现（FastAPI）2.1 运行环境2.2 目录结构建议2.3 serv
阅读更多...
C#实现千万数据秒级导入的代码

C#实现千万数据秒级导入的代码

《C#实现千万数据秒级导入的代码》在实际开发中excel导入很常见,现代社会中很容易遇到大数据处理业务,所以本文我就给大家分享一下千万数据秒级导入怎么实现,文中有详细的代码示例供大家参考,需要的朋友可... 目录前言一、数据存储二、处理逻辑优化前代码处理逻辑优化后的代码总结前言在实际开发中excel导入很
阅读更多...
Spring Security简介、使用与最佳实践

Spring Security简介、使用与最佳实践

《SpringSecurity简介、使用与最佳实践》SpringSecurity是一个能够为基于Spring的企业应用系统提供声明式的安全访问控制解决方案的安全框架,本文给大家介绍SpringSec... 目录一、如何理解 Spring Security？—— 核心思想二、如何在 Java 项目中使用？——
阅读更多...
SpringBoot+RustFS 实现文件切片极速上传的实例代码

SpringBoot+RustFS 实现文件切片极速上传的实例代码

《SpringBoot+RustFS实现文件切片极速上传的实例代码》本文介绍利用SpringBoot和RustFS构建高性能文件切片上传系统,实现大文件秒传、断点续传和分片上传等功能,具有一定的参考... 目录一、为什么选择 RustFS + SpringBoot？二、环境准备与部署2.1 安装 RustF
阅读更多...
Nginx部署HTTP/3的实现步骤

Nginx部署HTTP/3的实现步骤

《Nginx部署HTTP/3的实现步骤》本文介绍了在Nginx中部署HTTP/3的详细步骤,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录前提条件第一步：安装必要的依赖库第二步：获取并构建 BoringSSL第三步：获取 Nginx
阅读更多...
springboot中使用okhttp3的小结

springboot中使用okhttp3的小结

《springboot中使用okhttp3的小结》OkHttp3是一个JavaHTTP客户端,可以处理各种请求类型,比如GET、POST、PUT等,并且支持高效的HTTP连接池、请求和响应缓存、以及异... 在 Spring Boot 项目中使用 OkHttp3 进行 HTTP 请求是一个高效且流行的方式。
阅读更多...
MyBatis Plus实现时间字段自动填充的完整方案

MyBatis Plus实现时间字段自动填充的完整方案

《MyBatisPlus实现时间字段自动填充的完整方案》在日常开发中,我们经常需要记录数据的创建时间和更新时间,传统的做法是在每次插入或更新操作时手动设置这些时间字段,这种方式不仅繁琐,还容易遗漏,... 目录前言解决目标技术栈实现步骤1. 实体类注解配置2. 创建元数据处理器3. 服务层代码优化填充机制详
阅读更多...
Python实现Excel批量样式修改器(附完整代码)

Python实现Excel批量样式修改器(附完整代码)

《Python实现Excel批量样式修改器(附完整代码)》这篇文章主要为大家详细介绍了如何使用Python实现一个Excel批量样式修改器,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一... 目录前言功能特性核心功能界面特性系统要求安装说明使用指南基本操作流程高级功能技术实现核心技术栈关键函
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2