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

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。

相关文章

深入探索协同过滤：从原理到推荐模块案例

深入探索协同过滤：从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤（UserCF）2. 基于物品的协同过滤（ItemCF）3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代，推荐系统成为连接用户与内容的桥梁。本文聚焦于
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
AI(文生语音)-TTS 技术线路探索学习:从拼接式参数化方法到Tacotron端到端输出

AI(文生语音)-TTS 技术线路探索学习:从拼接式参数化方法到Tacotron端到端输出

AI(文生语音)-TTS 技术线路探索学习:从拼接式参数化方法到Tacotron端到端输出 在数字化时代，文本到语音（Text-to-Speech, TTS）技术已成为人机交互的关键桥梁，无论是为视障人士提供辅助阅读，还是为智能助手注入声音的灵魂，TTS 技术都扮演着至关重要的角色。从最初的拼接式方法到参数化技术，再到现今的深度学习解决方案，TTS 技术经历了一段长足的进步。这篇文章将带您穿越时
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
嵌入式方向的毕业生，找工作很迷茫

嵌入式方向的毕业生，找工作很迷茫

一个应届硕士生的问题： 虽然我明白想成为技术大牛需要日积月累的磨练，但我总感觉自己学习方法或者哪些方面有问题，时间一天天过去，自己也每天不停学习，但总感觉自己没有想象中那样进步，总感觉找不到一个很清晰的学习规划……眼看 9 月份就要参加秋招了，我想毕业了去大城市磨练几年，涨涨见识，拓开眼界多学点东西。但是感觉自己的实力还是很不够，内心慌得不行，总怕浪费了这人生唯一的校招机会，当然我也明白，毕业
阅读更多...
理解分类器（linear）为什么可以做语义方向的指导？（解纠缠）

理解分类器（linear）为什么可以做语义方向的指导？（解纠缠）

Attribute Manipulation（属性编辑）、disentanglement（解纠缠）常用的两种做法：线性探针和PCA_disentanglement和alignment-CSDN博客 在解纠缠的过程中，有一种非常简单的方法来引导G向某个方向进行生成，然后我们通过向不同的方向进行行走，那么就会得到这个属性上的图像。那么你利用多个方向进行生成，便得到了各种方向的图像，每个方向对应了很多
阅读更多...
轻松录制每一刻：探索2024年免费高清录屏应用

轻松录制每一刻：探索2024年免费高清录屏应用

你不会还在用一些社交工具来录屏吧？现在的市面上有不少免费录屏的软件了。别看如软件是免费的，它的功能比起社交工具的录屏功能来说全面的多。这次我就分享几款我用过的录屏工具。 1.福晰录屏大师 链接直达：https://www.foxitsoftware.cn/REC/  这个软件的操作方式非常简单，打开软件之后从界面设计就能看出来这个软件操作的便捷性。界面的设计简单明了基本一打眼你就会轻松驾驭啦
阅读更多...
深入探索嵌入式 Linux

深入探索嵌入式 Linux

摘要：本文深入探究嵌入式 Linux。首先回顾其发展历程，从早期尝试到克服诸多困难逐渐成熟。接着阐述其体系结构，涵盖硬件、内核、文件系统和应用层。开发环境方面包括交叉编译工具链、调试工具和集成开发环境。在应用领域，广泛应用于消费电子、工业控制、汽车电子和智能家居等领域。关键技术有内核裁剪与优化、设备驱动程序开发、实时性增强和电源管理等。最后展望其未来发展趋势，如与物联网融合、人工智能应用、安全性与
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2