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

article/2025/9/14 5:15:49

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");}

 


http://chatgpt.dhexx.cn/article/ON7tmSLk.shtml

相关文章

简单迷宫(递归)

简单迷宫(递归)

代码思路 1.创建二位数组作为迷宫 2.数字1为墙壁&#xff0c;2为经过的位置&#xff0c;3为死路&#xff0c;0为未探寻的位置 3,定义一个起点和终点&#xff0c;运用递归的方法&#xff0c;按照自己设计的寻找方向的优先级运行&#xff0c;直到让终点值为2则返回true&#x…
阅读更多...
简单迷宫问题

简单迷宫问题

简单迷宫问题 一、问题描述二、数据组织三、算法说明附录&#xff1a;完整代码 #简单迷宫问题 一、问题描述 给定一个MN得迷宫&#xff0c;求一条从指定入口到出口得迷宫路径。假设一个迷宫如图1所示&#xff0c;&#xff08;这里MN8)&#xff0c;其中每个方块用空白表示通道…
阅读更多...
maven生命周期表

maven生命周期表

阅读更多...
maven生命周期lifecycle和plugins介绍

maven生命周期lifecycle和plugins介绍

一、Maven的生命周期 生命周期的定义&#xff1a;Maven的生命周期就是为了对所有的构建过程进行抽象和统一。在大量项目的构建过程中&#xff0c;Maven总结出了一套高度完善的&#xff0c;易于扩展的生命周期&#xff0c;包括项目的清理&#xff0c;初始化&#xff0c;编译&am…
阅读更多...
【Maven】IDEA中Maven生命周期

【Maven】IDEA中Maven生命周期

Maven生命周期&#xff08;lifecycle&#xff09;由各个阶段组成&#xff0c;每个阶段由Maven的插件plugin来执行完成。 生命周期&#xff08;lifecycle&#xff09;主要包括clean、resources、complie、install、pacakge、testResources、testCompile、deploy等&#xff0c;其…
阅读更多...
Maven生命周期与插件

Maven生命周期与插件

竟无语凝噎 文章目录 前言一、生命周期二、插件总结 前言 maven原来有这么多道道 一、生命周期 Maven对项目构建的生命周期划分为三套 clean&#xff1a;清理工作 default&#xff1a;核心工作&#xff0c;例如编译&#xff0c;测试&#xff0c;打包&#xff0c;部署等 si…
阅读更多...
Maven 生命周期详解

Maven 生命周期详解

思考&#xff1a;我们常使用的maven命令&#xff0c;比如 mvn clean install&#xff0c;mvn clean package 这些命令到底最后是如何工作的&#xff1f; 在这里我们还是先一步步来&#xff0c;其实它们运行的是生命周期中对应的phase阶段。 Maven 拥有三套独立的生命周期&…
阅读更多...
关于maven生命周期的理解

关于maven生命周期的理解

晚上有点无聊&#xff0c;看到了一些东西引发了自己的思路&#xff0c;就想将maven的一些东西总结总结&#xff0c;有从网上抄的&#xff0c;也有自己的思路。 一、生命周期是指什么&#xff08;lifecycle&#xff09; Maven的生命周期就是对所有的构建过程进行抽象和统一。包…
阅读更多...
Maven的生命周期

Maven的生命周期

一、生命周期简介&#xff1a; Maven强大的一个重要的原因是它有一个十分完善的生命周期模型&#xff0c;这个生命周期可以从两方面来理解&#xff1a; 运行Maven的每个步骤都由它来定义的&#xff0c;这种预定义的默认行为使得我们使用Maven变得简单。 这个模型是一种标准&am…
阅读更多...
Maven 生命周期

Maven 生命周期

1. Maven 构建生命周期 Maven 构建生命周期就是 Maven 将一个整体任务划分为一个个的阶段&#xff0c;类似于流程图&#xff0c;按顺序依次执行。也可以指定该任务执行到中间的某个阶段结束。Maven 的内部有三个构建生命周期&#xff0c;分别是 clean, default, site。其中 def…
阅读更多...
Maven生命周期

Maven生命周期

Maven生命周期 个人网站 https://blog.deschen.cn/ 文章目录 Maven生命周期一、Maven生命周期的定义二、Maven三套独立的生命周期三、Maven的插件 一、Maven生命周期的定义 Maven的生命周期就是为了对所有的构建过程进行抽象和统一。包括项目的清理&#xff0c;初始化&#x…
阅读更多...
Maven —— 生命周期

Maven —— 生命周期

每个生命周期的各个环节都是由各种插件完成&#xff01;&#xff01;&#xff01;Maven有三个相互独立的生命周期&#xff08;Maven的这三个生命周期不能看成一个整体&#xff09;&#xff01;&#xff01;&#xff01; mvn clean&#xff1a;清理编译的项目mvn compile&#x…
阅读更多...
代码统计利器--CLOC

代码统计利器--CLOC

MAC下安装命令:$ brew install cloc其他的linux安装 $ aptitude install cloc使用方法.到目录下运行: $ cloc .The default output will show you a breakdown by language. Here’s an example of what it’ll look like: php much? You can, of course, customize the poop …
阅读更多...
代码统计工具cloc使用

代码统计工具cloc使用

简介 CLOC(Count Lines of Code)&#xff0c;是一个可以统计多种编程语言中空行、评论行和物理行的工具。这个工具还是蛮实用的&#xff0c;可以帮我们快速了解一个项目中代码的信息。 安装使用 windows 10 win10下可以去github上下载其最新版&#xff0c;截止本文时&#…
阅读更多...
windows代码量计算开源工具cloc安装和使用教程

windows代码量计算开源工具cloc安装和使用教程

windows代码量计算开源工具cloc 下载cloc使用cloc 下载cloc cloc下载地址: https://github.com/AlDanial/cloc/releases. 选择exe版本的&#xff0c;也可以下载我上传的1.90版本链接: 点击跳转下载地址 使用cloc 下载好cloc-1.90.exe之后&#xff0c;重命名未cloc.exe&…
阅读更多...
Linux统计代码量命令cloc

Linux统计代码量命令cloc

记录一下Linux中一个非常好用的代码量统计命令&#xff1a;cloc 安装步骤&#xff1a; sudo apt-get install cloc使用方法&#xff1a; 进入到要统计的工程根目录&#xff1a; cloc .运行结果:
阅读更多...
Windows环境下用cloc统计代码量

Windows环境下用cloc统计代码量

cloc一款开源代码统计工具&#xff0c;支持windows和Linux环境。能统计指定文件夹或文件夹中文件数files、空白行数blank、注释行数comment和代码行数code。今天介绍windows环境下的使用方法。 使用简单&#xff1a; 下载&#xff1a; Releases AlDanial/cloc (github.com)…
阅读更多...
代码统计工具CLOC的使用

代码统计工具CLOC的使用

简介 CLOC(Count Lines of Code)&#xff0c;是一个可以统计多种编程语言中空行、评论行和物理行的工具。这个工具还是蛮实用的&#xff0c;可以帮我们快速了解一个项目中代码的信息。 安装使用 windows 10 win10下可以去github上下载其最新版&#xff0c;截止本文时&#…
阅读更多...
cloc 代码统计工具

cloc 代码统计工具

安装 yum -y install cloc使用 [rootnode1 new-website]# cloc .135 text files.134 unique files.20 files ignored.github.com/AlDanial/cloc v 1.70 T3.63 s (32.0 files/s, 26416.0 lines/s) ------------------------------------------------------------------------…
阅读更多...
10分钟掌握高效代码行统计工具——cloc

10分钟掌握高效代码行统计工具——cloc

cloc 一款高效的代码行统计工具&#xff0c;且跨多平台&#xff1a; WindowLinuxMac… … 高效是其优点&#xff0c;且稳定性比较好。 Linux版的可以处理超大工程的文件&#xff0c;不会出现其它同类工具在处理超大文件时崩溃的问题。 用法简单&#xff0c;学习成本低&…
阅读更多...
推荐文章

Copyright @ 2022~2023