[数据结构]迷宫问题求解

目录

数据结构——迷宫问题求解::

                                                    1.迷宫问题

                                                    2.迷宫最短路径问题

                 


数据结构——迷宫问题求解::

1.迷宫问题

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef struct Point
{int row;int col;
}PT;
typedef PT STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;
void StackInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = ps->capacity = 0;
}
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
void StackDestory(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;
}
//数据结构建议不要直接访问结构体数据,一定要通过函数接口访问
//解耦:高内聚,低耦合
void StackPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;
}
void StackPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));ps->top--;
}
STDataType StackTop(ST* ps)
{assert(ps);//为空不能访问栈顶元素assert(!StackEmpty(ps));return ps->a[ps->top - 1];
}
int StackSize(ST* ps)
{assert(ps);return ps->top;
}
ST path;
void PrintPath(ST* ps)
{ST rPath;StackInit(&rPath);while (!StackEmpty(ps)){StackPush(&rPath, StackTop(ps));StackPop(ps);}while (!StackEmpty(&rPath)){PT top = StackTop(&rPath);printf("(%d,%d)\n", top.row, top.col);StackPop(&rPath);}StackDestory(&rPath);
}
bool IsPass(int** maze, int N, int M, PT pos)
{if (pos.row >= 0 && pos.row < N&& pos.col >= 0 && pos.col < M&& maze[pos.row][pos.col] == 0){return true;}else{return false;}
}
bool GetMazePath(int** maze, int N, int M, PT cur)
{StackPush(&path, cur);//如果走到出口if (cur.row == N - 1 && cur.col == M - 1){return true;}//探测cur位置上下左右四个方向PT next;maze[cur.row][cur.col] = 2;//探测上next = cur;next.row -= 1;if (IsPass(maze, N, M, next)){if (GetMazePath(maze, N, M, next))return true;}//探测下next = cur;next.row += 1;if (IsPass(maze, N, M, next)){if (GetMazePath(maze, N, M, next))return true;}//探测左next = cur;next.col -= 1;if (IsPass(maze, N, M, next)){if (GetMazePath(maze, N, M, next))return true;}//探测右next = cur;next.col += 1;if (IsPass(maze, N, M, next)){if (GetMazePath(maze, N, M, next))return true;}StackPop(&path);return false;
}
int main()
{int N = 0;int M = 0;while (scanf("%d %d", &N, &M) != EOF){//动态开辟二维数组int** maze = (int**)malloc(sizeof(int*) * N);for (int i = 0; i < N; i++){maze[i] = (int*)malloc(sizeof(int) * M);}//二维数组的输入for (int i = 0; i < N; i++){for (int j = 0; j < M; j++){scanf("%d", &maze[i][j]);}}StackInit(&path);//PrintMaze(maze, N, M);PT entry = { 0,0 };if (GetMazePath(maze, N, M, entry)){PrintPath(&path);}StackDestory(&path);//二维数组的销毁for (int i = 0; i < N; i++){free(maze[i]);maze[i] = NULL;}free(maze);maze = NULL;}return 0;
}

2.迷宫最短路径问题

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef struct Point
{int row;int col;
}PT;
typedef PT STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;
void StackInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = ps->capacity = 0;
}
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
void StackDestory(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;
}
//数据结构建议不要直接访问结构体数据,一定要通过函数接口访问
//解耦:高内聚,低耦合
void StackPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;
}
void StackPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));ps->top--;
}
STDataType StackTop(ST* ps)
{assert(ps);//为空不能访问栈顶元素assert(!StackEmpty(ps));return ps->a[ps->top - 1];
}
int StackSize(ST* ps)
{assert(ps);return ps->top;
}
ST path;
ST minPath;
void PrintPath(ST* ps)
{ST rPath;StackInit(&rPath);while (!StackEmpty(ps)){StackPush(&rPath, StackTop(ps));StackPop(ps);}while (StackSize(&rPath) > 1){PT top = StackTop(&rPath);printf("[%d,%d],", top.row, top.col);StackPop(&rPath);}PT top = StackTop(&rPath);printf("[%d,%d]\n", top.row, top.col);StackPop(&rPath);StackDestory(&rPath);
}
bool IsPass(int** maze, int N, int M, PT pos)
{if (pos.row >= 0 && pos.row < N&& pos.col >= 0 && pos.col < M&& maze[pos.row][pos.col] == 1){return true;}else{return false;}
}
void StackCopy(ST* ppath, ST* pcopy)
{pcopy->a = (STDataType*)malloc(sizeof(STDataType) * ppath->capacity);memcpy(pcopy->a, ppath->a, sizeof(STDataType) * ppath->top);pcopy->top = ppath->top;pcopy->capacity = ppath->capacity;
}
void GetMazePath(int** maze, int N, int M, PT cur, int P)
{StackPush(&path, cur);//如果走到出口if (cur.row == 0 && cur.col == M - 1){if (P >= 0 && StackEmpty(&minPath)|| StackSize(&path) < StackSize(&minPath)){StackDestory(&minPath);StackCopy(&path, &minPath);}}//探测cur位置上下左右四个方向PT next;maze[cur.row][cur.col] = 2;//探测上next = cur;next.row -= 1;if (IsPass(maze, N, M, next)){GetMazePath(maze, N, M, next, P - 3);          }//探测下next = cur;next.row += 1;if (IsPass(maze, N, M, next)){GetMazePath(maze, N, M, next, P);     }//探测左next = cur;next.col -= 1;if (IsPass(maze, N, M, next)){GetMazePath(maze, N, M, next, P - 1);}//探测右next = cur;next.col += 1;if (IsPass(maze, N, M, next)){GetMazePath(maze, N, M, next, P - 1);}maze[cur.row][cur.col] = 1;StackPop(&path);
}
int main()
{int N = 0;int M = 0;int P = 0;while (scanf("%d %d %d", &N, &M, &P) != EOF){//动态开辟二维数组int** maze = (int**)malloc(sizeof(int*) * N);for (int i = 0; i < N; i++){maze[i] = (int*)malloc(sizeof(int) * M);}//二维数组的输入for (int i = 0; i < N; i++){for (int j = 0; j < M; j++){scanf("%d", &maze[i][j]);}}StackInit(&path);StackInit(&minPath);//PrintMaze(maze, N, M);PT entry = { 0,0 };GetMazePath(maze, N, M, entry, P);if (!StackEmpty(&minPath)){PrintPath(&minPath);}else{printf("Can not escape!\n");}StackDestory(&path);StackDestory(&minPath);//二维数组的销毁for (int i = 0; i < N; i++){free(maze[i]);maze[i] = NULL;}free(maze);maze = NULL;}return 0;
}

                 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/152378.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

拼多多API接口的使用方针如下:

了解拼多多API接口 拼多多API接口是拼多多网提供的一种应用程序接口&#xff0c;允许开发者通过程序访问拼多多网站的数据和功能。通过拼多多API接口&#xff0c;开发者可以开发各种应用程序&#xff0c;如店铺管理工具、数据分析工具、购物比价工具等。在本章中&#xff0c;我…

1.6 IntelliJ IDEA开发工具

前言&#xff1a; ### 1.6 IntelliJ IDEA开发工具笔记 - **背景**&#xff1a; - 使用基础文本编辑器如记事本编写Java代码虽然可行&#xff0c;但存在效率低下且难以调试的问题。 - 集成开发环境 (IDE) 可以有效地提高Java程序的开发效率。 - **常见Java IDE**&#xf…

基于springboot实现自习室预订系统的设计与实现项目【项目源码+论文说明】

基于springboot实现自习室预订系统的设计与实现演示 摘要 在网络高速发展的时代&#xff0c;众多的软件被开发出来&#xff0c;给学生带来了很大的选择余地&#xff0c;而且人们越来越追求更个性的需求。在这种时代背景下&#xff0c;学院只能以学生为导向&#xff0c;所以自习…

C# 通过winmm枚举音频设备

文章目录 前言一、如何实现&#xff1f;1、添加依赖&#xff08;1&#xff09;、nuget安装winmm的封装库&#xff08;2&#xff09;、补充接口2、定义实体3、实现枚举 二、完整代码三、使用示例总结 前言 使用C#做音频录制时需要获取音频设备信息&#xff0c;比如使用ffmpeg进…

R | R包默认安装路径的查看及修改

R | R包默认安装路径的查看及修改 一、R包安装位置查看二、已安装R包查询三、R包安装位置修改四、R包安装位置永久修改 在【R: R package安装的几种方式】【R: R版本更新及R包迁移&#xff08;详细步骤&#xff09;】两篇文章中介绍过R包的常见安装方式&#xff0c;以及在不同R…

STM32实战项目——WIFI远程开关灯

前言 其实WIFI开关灯在几个月前就想做了&#xff0c;但是对于没有云平台调试经验的我&#xff0c;一开始有些摸不着头脑&#xff0c;所以就搁置了。十一假期与老同学聊天时了解到他也在做一个远程开关灯的小项目&#xff0c;所以就重新开始了WIFI远程开关灯的小项目。 本文使用…

学习Consul中踩过的坑

一、杀不死的consul 通过mac的homebrew安装了consul以后&#xff0c;手动启动consul报8300端口已被占用&#xff0c;通过lsof -i:8300和lsof -i:8500查看端口占用情况&#xff0c;发现consul已经启动了。然后手动kill -9对应的进程id&#xff0c;再启动consul&#xff0c;还是…

ChatGPT私有数据结合有什么效果?它难吗?

ChatGPT的出现可谓是惊艳了全世界&#xff0c;ChatGPT的问答能力通过了图灵测试&#xff0c;使其回答问题的方式与人类几乎无法区分。大家不甘于只在官方的对话页面问答&#xff0c;想利用 GPT 模型的自然语言能力结合私有数据开拓更多的应用场景。 | ChatGPT私有数据结合特点 …

[Java] 服务端消息推送汇总

前言&#xff1a;当构建实时消息推送功能时&#xff0c;选择适合的方案对于开发高效的实时应用至关重要。消息的推送无非就推、拉两种数据模型。本文将介绍四种常见的消息实时推送方案&#xff1a;短轮询&#xff08;拉&#xff09;、长轮训&#xff08;拉&#xff09;、SSE&am…

c++视觉处理---高斯滤波

高斯滤波处理 高斯滤波是一种常用的平滑滤波方法&#xff0c;它使用高斯函数的权重来平滑图像。高斯滤波通常用于去除噪声并保留图像中的细节。在OpenCV中&#xff0c;可以使用cv::GaussianBlur()函数来应用高斯滤波。 以下是cv::GaussianBlur()函数的基本用法&#xff1a; …

vue实现echarts中 9种 折线图图例

let datas [{ DivideScore: 7, UserScore: 7.2, Name: 目标制定 },{ DivideScore: 7, UserScore: 7, Name: 具体性 },{ DivideScore: 7, UserScore: 7.5, Name: 可衡量性 },{ DivideScore: 7, UserScore: 7, Name: 可实现性 },{ DivideScore: 7, UserScore: 7, Name: 时间限定…

简单强大的时序图绘制工具

今天分享一个简单强大的时序图绘制工具——WaveDrom。 WaveDrom Digital Timing Diagram everywhere WaveDrom draws your Timing Diagram or Waveform from simple textual description. It comes with description language, rendering engine and the editor. WaveDrom edi…

基于Springboot实现房屋租赁租房平台系统项目【项目源码+论文说明】

基于Springboot实现房屋租赁租房平台系统演示 摘要 在网络高速发展的时代&#xff0c;众多的软件被开发出来&#xff0c;给用户带来了很大的选择余地&#xff0c;而且人们越来越追求更个性的需求。在这种时代背景下&#xff0c;房东只能以用户为导向&#xff0c;所以开发租房网…

MongoDB-介绍与安装部署

介绍与安装部署 1.MongoDB简介a) 体系结构b) 数据模型c) MongoDB的特点c.1) 高性能c.2) 高性可用性c.3) 高拓展性c.4) 丰富的查询支持 2.单机部署a) Windows系统中的安装启动b) Shell连接(mongo命令)c) Linux系统中的安装启动和连接 1.MongoDB简介 MongoDB是一个开源、高性能、…

【网络安全入门】学习网络安全必须知道的100 个网络基础知识

前言 话不多说&#xff0c;完整的资料已经上传至CSDN官方&#xff0c;需要的可以点击链接自取【282G】网络安全&黑客技术零基础到进阶全套学习大礼包&#xff0c;免费分享&#xff01; 1 什么是链接? 链接是指两个设备之间的连接。它包括用于一个设备能够与另一个设备…

k8s containerd查看镜像

直接查看crictl image会报错&#xff1a; 1) crictl config runtime-endpoint unix:///run/containerd/containerd.sock 2) vi /etc/crictl.yaml 3) systemctl daemon-reload 此时&#xff0c;再查看image:

Python —— UI自动化之八大元素定位

1、基础元素定位 1、id定位 使用html中标签的id元素去定位&#xff0c;在一般定位中优先选择&#xff0c;举例&#xff1a; from time import sleep from selenium import webdriver from selenium.webdriver.common.by import Bydriver webdriver.Firefox() driver.get(&q…

CI/CD工具中的CI和CD的含义

CI/CD工具中的CI和CD的含义&#xff1f; CI/CD 是现代软件开发方法中广泛使用的一种方法。其中&#xff0c;CI 代表持续集成&#xff08;Continuous Integration&#xff09;&#xff0c;CD 则有两层含义&#xff0c;一是持续交付&#xff08;Continuous Delivery&#xff09;…

Pyside6 QPushButton

Pyside6 QPushButton QPushButton使用QPushButton继承关系QPushButton的函数(Function)和信号(Signal)QPushButton信号 QPushButton例程界面设计clicked信号测试pressed信号测试released信号测试toggled信号测试按键长按测试按键长按间隔测试完整程序界面程序主程序 按键或命令…

redis学习(二)——redis常见命令及基础数据类型

数据类型 基础数据类型 字符串 String abcMap集合 Hsah {name:“zhangsan”,age:18}列表 List [a, b, c, d]Set集合 Set {a,b,c}有序Set集合 SortSet {a:1,b:2,c:3} 特殊数据类型 GEO 地理坐标 {A:(100.2,35.1)}BitMap 位图&#xff0c;只存储0和1 01101011101HyperLog 基数…