数据结构——八方向探索迷宫问题解答

2024-04-02 17:38
文章标签 数据结构 方向 探索 迷宫 问题解答

本文主要是介绍数据结构——八方向探索迷宫问题解答，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/*

 水平有限，仅供参考

题目要求：用c语言动态演示如何走出带颜色的迷宫，并输出路径。要求探测八个方向，动态生成迷宫大小，路径用队列来存储，输出路径时用栈完成。

*/


#include<stdio.h>

typedef int ElemType;
typedef struct Data{
int r,c;  // 迷宫的行列
ElemType e;   // 上一个可通过迷宫在三元组中的位置
}SElemType,QElemType;    
#include<stdio.h>
#include"MStack.h"  // 栈的头文件
#include"MQueue.h"  // 队列的头文件
#include<stdlib.h>
#include<time.h>
#include<windows.h>


ElemType** createPuzzle(int ,int );  //   随机产生迷宫
Status rand(ElemType **,int ,int );  // 随机产生迷宫障碍物
Status showPuzzle(ElemType **, int , int );  // 输出迷宫
Status printPuzzle(ElemType **,SqStack *, int , int );  // 打印迷宫
ElemType findPath(ElemType **,ElemType **,QNode *,int i,int j,int d[][2]);   // 判断8个方向是否可以通行，并入队列
Status PushData(QNode ,SqStack *);   //  将通过的路径放进栈
int num=1;
void main(){         //   ========================   主函数    ================================================


int r,c;  //  随机产生迷宫的大小
int flag;  // 判断是否走出了迷宫
int k;
int Directrion[8][2]={{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1},{1,0}};   // 逆时针方向寻找路径
ElemType **m=NULL,**mark=NULL;
SqStack *s,s1;
QNode *Q,q;
Q=&q;s=&s1;
    InitQueue(Q); // 初始化 ======
InitStack(s);
printf("请输入迷宫的大小!\n");
scanf("%d%d",&r,&c);
r=r+2;c=c+2;  // 迷宫外部需要加上墙，所以数组大小加2（上下，左右）
m=createPuzzle(r,c);  // 动态产生迷宫 m 
mark=createPuzzle(r,c);   // 标记走过的位置
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
mark[i][j]=false;   //  false 表示没有走过的位置
rand(m,r,c);  // 随机产生迷宫障碍物
flag=findPath(m,mark,Q,r,c,Directrion);  // 寻找路径
if(flag==1){    // 可以走出迷宫
PushData(q,s);
k=s->top;
k++;
for(int i=0;i<k;i++){
system("cls");
printPuzzle(m,s,r,c);  // 打印迷宫
num++;
Sleep(500);
}
StackTraverse(s1);   // 输出坐标
}
else
{
showPuzzle(m,r,c);
printf("No Path!\n");
}



}




ElemType** createPuzzle(int row,int column){  // 实现 创建矩阵 函数
ElemType **a;
a = (int **)malloc(sizeof(int *) * row);//分配指针数组
for(int i=0; i<row; i++)
{
a[i] = (int *)malloc(sizeof(int) * column);//分配每个指针所指向的数组
}
return a;
}

Status rand(ElemType **p,int row,int column){ // 随机产生迷宫
srand(unsigned(time(NULL)));
int r,c;
for(r=0;r<row;r++)   
for(c=0;c<column;c++){
if(r==0||c==0||r==row-1||c==column-1){   // 数组的第一行最后一行第一列最后一列均为墙
p[r][c]=1;
}
else{
p[r][c]=rand()%100;
if(p[r][c]>=40)
p[r][c]=0;    // 0 表示课通过 
else
p[r][c]=1;
}
}
p[1][1]=0;  //起点
p[row-2][column-2]=0;  // 终点
return OK;
}

Status printPuzzle(ElemType **m,SqStack *s, int row, int column){  // 打印迷宫
SElemType *data,data1;
int k=s->top;    // 记录栈元素的总个数
int num1=0;
int flag=1;
data=&data1;
for(int i=0;i<row;i++){
for(int j=0;j<column;j++){
if(i==0||j==0||i==row-1||j==column-1||m[i][j]==1){   //  输出迷宫墙
SetConsoleTextAttribute(GetStdHandle((STD_OUTPUT_HANDLE)),7);
printf("■");}
else{
data->r=i;
data->c=j;
if(searchStackData(s,data1)&&flag==1){
SetConsoleTextAttribute(GetStdHandle((STD_OUTPUT_HANDLE)),10);

printf("※");
num1++;
if(num1==num)
flag=0;
}
else{
printf("  ");
}
s->top=k;
}
}
printf("\n");  
}
return OK;
}


ElemType findPath(ElemType **m,ElemType **mark,QNode *Q,int row,int column,int d[][2]){          //     寻找路径  
SElemType *data,data1,data2;   //data2用于记录向不同方向探索的坐标
int flag=0;  // 判断是否走出迷宫
data=&data1;
data->c=1;  // 起点纵坐标
data->r=1;  // 起点横坐标
data->e=-1;  // 代表没有前一个元素 
EnQueue(Q,data1);  // 起点入队列
while(Q->front!=Q->rear){   // 队列非空 
int i,j;
DeQueue(Q,data);
i=data->r;  // 将行列赋给i j 便于加上方向判断是否有路径
j=data->c;
mark[i][j]=true;  // 表示已经走过
data2=data1;
data2.e=Q->front;   // 记录上个开始探索方向的初始位置
if((i==row-2)&&(j==column-2))   // 走出迷宫
{ flag=1;
 break;}
for(int k=0;k<8;k++){   // 搜索八个方向
i=data->r;j=data->c;
i+=d[k][0];j+=d[k][1];
if(m[i][j]==1||mark[i][j]==true)   // 遇见路障或者已在队列里
continue;
else{
data2.r=i;data2.c=j;
mark[i][j]=true;
EnQueue(Q,data2); // 找到通路，入队
}
} // for
Q->front++;
}  //while
return flag;
}


Status PushData(QNode q,SqStack *s){   //  将通过的路径放进栈
SElemType data1;
int i;
i=q.front;  // 上一个元素的位置
while(i!=-1){    // 起点的值为 -1
data1=q.base[i];
Push(s,data1);  // 坐标入栈
i=q.base[i].e;
}
return OK;
}


showPuzzle(ElemType **m, int row, int column){
SElemType *data,data1;
data=&data1;
for(int i=0;i<row;i++){
for(int j=0;j<column;j++){
if(i==0||j==0||i==row-1||j==column-1||m[i][j]==1)    //  输出迷宫墙
printf("■");
else
printf("  ");
}
printf("\n");  
}
return OK;

}

/* ==================================================            栈的头文件     ==========================================================*/

#ifndef _MSTACK_H_  
#define _MSTACK_H_


/* 如果没有定义_MSTACK_H_，则定义_MSTACK_H_，
并编译下面的代码部分，直到遇到#endif。这样，当重复引用时，
由于_MSTACK_H_已经被定义，则下面的代码部分就不会被编译了，
这样就避免了重复定义。  */


#include<windows.h>
#define STACK_INIT_SIZE 12500  // 存储空间初始分配量
#define STACKINCREMENT 10  // 存储空间分配增量
#define true 1
#define false 0
#define OK 1
#define OVERFLOW -1


typedef int Status; //函数返回类型，其值为结果状态码


 struct stack1{
SElemType base[STACK_INIT_SIZE];
int top;  //指示栈顶位置
};
 typedef struct stack1 SqStack;


 


Status Push(SqStack *s,SElemType data){      //  元素入栈
if(s->top==STACK_INIT_SIZE-1)
return OVERFLOW;
else{
s->top++;
s->base[(s->top)]=data;
}
return OK;


}


Status Pop(SqStack *s,SElemType *data){      //  栈顶元素出栈
if(s->top==-1)
return OVERFLOW;
else{
*data=s->base[s->top];
s->top--;
}
return OK;

}






Status Get(SqStack *s,SElemType *data){   // 得到栈顶元素
if(s->top==-1)
return OVERFLOW;
else{
*data=s->base[s->top];
}
return OK;

}


Status StackEmpty(SqStack *s){     //  判断栈是否为空
if(s->top==-1)
   return true;
else
    return false;


}


Status InitStack(SqStack *s){    //    初始化栈
s->top=-1;
if(!s->base)
return OVERFLOW;
return OK;

}


Status StackTraverse(SqStack s){         //栈元素的遍历
if(s.top==-1){
printf("栈已空!\n");
return OK;
}
while(s.top!=-1){
SetConsoleTextAttribute(GetStdHandle((STD_OUTPUT_HANDLE)),5);
printf("<%d:%d> ",s.base[s.top].r,s.base[s.top].c);  // 输出坐标
s.top--;
}
printf("\n");
SetConsoleTextAttribute(GetStdHandle((STD_OUTPUT_HANDLE)),7);
return OK;
}


Status searchStackData(SqStack *s,SElemType data){
while(s->top>=0){
if((s->base[s->top].r==data.r)&&(s->base[s->top].c==data.c))
return true;
s->top--;
}
return false;
}

#endif

/* ==================================================            队列的头文件     ==========================================================*/

#ifndef _MQUEUE_H_  
#define _MQUEUE_H_


/* 如果没有定义_MQUEUE_H_，则定义_MQUEUE_H_，
并编译下面的代码部分，直到遇到#endif。这样，当重复引用时，
由于_MQUEUE_H_已经被定义，则下面的代码部分就不会被编译了，
这样就避免了重复定义。  */




#include<malloc.h>
#include<stdlib.h>


#define ERROR 0   // 函数结果状态码
#define OK 1
#define OVERFLOW -1
#define true 1
#define false 0
#define STACK_INIT_SIZE 12500


typedef int Status;   // 函数返回值类型




typedef struct QUeue1{
QElemType base[STACK_INIT_SIZE];    
int front;  // 队头
int rear;  // 队尾
}QNode;




Status InitQueue(QNode *Q){  // 初始化队列
Q->front=0;  
Q->rear=0;
if(!Q->base)
return OVERFLOW;
return OK;
}


 Status QueueEmpty(QNode *Q){  // 判断队列是否为空
if(Q->front==Q->rear)
   return true;
else
    return false;
 }


Status EnQueue(QNode *Q,QElemType data){  // 入队列
if(Q->rear==STACK_INIT_SIZE-1)
return OVERFLOW;
else{
Q->base[(Q->rear)]=data;
Q->rear++;  //指向下一个元素
}
return OK;
}


Status DeQueue(QNode *Q,QElemType *data){  // 出队列,队列不为空,返回其值
if(Q->front==Q->rear)
return OVERFLOW;
else{
*data=Q->base[Q->front];

}
return OK;
}


#endif



这篇关于数据结构——八方向探索迷宫问题解答的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

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

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

本文通过观察对象的内存布局，跟踪函数调用的汇编代码。分析了C++对象内存的布局情况，虚函数的执行方式，以及虚继承，等等 文章链接：http://dev.yesky.com/254/2191254.shtml      论C/C++函数间动态内存的传递 (2005-07-30)   当你涉及到C/C++的核心编程的时候，你会无止境地与内存管理打交道。 文章链接：http://dev.yesky
阅读更多...
探索蓝牙协议的奥秘：用ESP32实现高质量蓝牙音频传输

探索蓝牙协议的奥秘：用ESP32实现高质量蓝牙音频传输

蓝牙（Bluetooth）是一种短距离无线通信技术，广泛应用于各种电子设备之间的数据传输。自1994年由爱立信公司首次提出以来，蓝牙技术已经经历了多个版本的更新和改进。本文将详细介绍蓝牙协议，并通过一个具体的项目——使用ESP32实现蓝牙音频传输，来展示蓝牙协议的实际应用及其优点。 蓝牙协议概述 蓝牙协议栈 蓝牙协议栈是蓝牙技术的核心，定义了蓝牙设备之间如何进行通信。蓝牙协议
阅读更多...
探索Elastic Search：强大的开源搜索引擎，详解及使用

探索Elastic Search：强大的开源搜索引擎，详解及使用

🎬 鸽芷咕：个人主页  🔥 个人专栏: 《C++干货基地》《粉丝福利》 ⛺️生活的理想，就是为了理想的生活! 引入 全文搜索属于最常见的需求，开源的 Elasticsearch （以下简称 Elastic）是目前全文搜索引擎的首选，相信大家多多少少的都听说过它。它可以快速地储存、搜索和分析海量数据。就连维基百科、Stack Overflow、
阅读更多...
【数据结构】线性表：顺序表

【数据结构】线性表：顺序表

文章目录 1. 线性表2. 顺序表2.1 概念及结构2.2 接口实现2.3 顺序表的问题及思考 1. 线性表 线性表是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式
阅读更多...
数据结构9——排序

数据结构9——排序

一、冒泡排序 冒泡排序（Bubble Sort），顾名思义，就是指越小的元素会经由交换慢慢“浮”到数列的顶端。 算法原理 从左到右，依次比较相邻的元素大小，更大的元素交换到右边；从第一组相邻元素比较到最后一组相邻元素，这一步结束最后一个元素必然是参与比较的元素中最大的元素；按照大的居右原则，重新从左到后比较，前一轮中得到的最后一个元素不参4与比较，得出新一轮的最大元素；按照上述规则，每一轮结
阅读更多...
算法与数据结构面试宝典——回溯算法详解（C#，C++）

算法与数据结构面试宝典——回溯算法详解（C#，C++）

文章目录 1. 回溯算法的定义及应用场景2. 回溯算法的基本思想3. 递推关系式与回溯算法的建立4. 状态转移方法5. 边界条件与结束条件6. 算法的具体实现过程7. 回溯算法在C#，C++中的实际应用案例C#示例C++示例 8. 总结回溯算法的主要特点与应用价值 回溯算法是一种通过尝试各种可能的组合来找到所有解的算法。这种算法通常用于解决组合问题，如排列、组合、棋盘游
阅读更多...
嵌入式学习——数据结构（哈希、排序）——day50

嵌入式学习——数据结构（哈希、排序）——day50

1. 查找二叉树、搜索二叉树、平衡二叉树 2. 哈希表——人的身份证——哈希函数 3. 哈希冲突、哈希矛盾 4. 哈希代码 4.1 创建哈希表 4.2  5. 算法设计 5.1 正确性 5.2 可读性（高内聚、低耦合） 5.3 健壮性 5.4 高效率（时间复杂度）时间复杂度越低，效率越高， 5.5 低储存（空间复杂度）空间复杂度越低，存储空间越少 6.排序算法 6.1 冒
阅读更多...
【数据结构与算法 经典例题】使用队列实现栈（图文详解）

【数据结构与算法 经典例题】使用队列实现栈（图文详解）

💓 博客主页：倔强的石头的CSDN主页               📝Gitee主页：倔强的石头的gitee主页    ⏩ 文章专栏：《数据结构与算法 经典例题》C语言                                   期待您的关注 ​​ 目录  一、问题描述 二、前置知识 三、解题思路 四、C语言实现代码 🍃队列实现代码：
阅读更多...
数据结构：二叉树详解 c++信息学奥赛基础知识讲解

数据结构：二叉树详解 c++信息学奥赛基础知识讲解

目录 一、二叉树的定义 二、二叉树的形态 三、二叉树的性质 四、二叉树的存储 五、二叉树的创建与遍历（递归） 六、二叉树实现 创建二叉树 展示二叉树 1、计算数的高度 2、计算数的叶子数量 3、计算数的宽度 4、层次遍历 5、前序遍历 递归写法 非递归写法 6、中序遍历 递归写法 非递归写法 7、后序遍历 递归写法 非递归写法 8、输出根节点到所有叶
阅读更多...
Java数据结构4-链表

Java数据结构4-链表

1. ArrayList的缺陷 由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java集合中又引入了LinkedList，即链表结构。 2. 链表 2.1 链表的概念及结构 链表是一种物理存储结构上非连续存储结构，数据元素
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2