26. 机器人走迷宫

embedded/2024/12/30 19:19:17/

在这里插入图片描述
在这里插入图片描述
、
在这里插入图片描述
在这里插入图片描述

一、问题分析

首先读题,仔细看描述中的内容,发现需求是

1.房间由X*Y的方格组成,每一个方格以(x,y)描述

2.机器人固定从方格(0,0)出发,只能向东或者向北前进。

3.出口固定为房间的最东角,(x-1,y-1)

4.用例保证机器人可以从入口走到出口

5.有些方格是墙壁,机器人不能经过

6.有些地方是一旦到达就无法走到出口的,如标记为B的方格,称之为陷阱方格

7.有些地方是机器人无法到达的,如标记为A的方格,称之为不可达方格,不可达方格不包括墙壁所在的位置。

8.为该机器人实现路径规划功能:给定房间大小、墙壁位置,请计算出陷阱方格与不可达方格分别有多少个。

9.输入描述:第一行为房间的X和Y,X,Y大于0小于等于1000

第二行为房间中墙壁的个数N(N大于等于0小于X*Y)

接着下面会有N行墙壁的坐标

同一行中如果有多个数据以一个空格隔开,用例保证所有的输入数据均合法(结尾不带回车换行)

10.输出描述:陷阱方格与不可达方格数量,两个信息在一行中输出,以一个空格隔开。(结尾不带回车换行)

二、解题思路

1.首先我们定义一个结构体Maze,其中包括

typedef struct {

        int **map; 一个二维数组map用来表示迷宫地图,如果0表示可以通过,1表示墙壁,2表示已访问,3表示陷阱(无法到达终点)

        int height; 表示迷宫高度

        int width;表示迷宫宽度

        int trapCount;表示陷阱数量

        int unreachableCount;表示不可达方格数量(需要最后才能知道)

        bool reachend;

} Maze;

2.然后我们需要一个函数用于初始化迷宫需要的参数有width和height

Maze* createMaze(int height, int width) {

Maze *maze = (Maze *)malloc(sizeof(Maze)); //首先分配内存

maze->height = height;

maze->width = width;

maze->trapCount = 0;

maze->unreachableCount = 0;

还需要为map分配内存

maze->map = (int **)malloc(sizeof(int *) * height);

for(int i = 0; i < height; i++) {

maze->map[i] = (int *)malloc(sizeof(int) * width);

for(int j = 0; j < width; j++) {

maze->map[i][j] = 0;

}

maze->reachend = false;

}

最后返回我们初始化好的maze

return maze;

}

3.因为我们为maze迷宫结构体分配了内存,我们需要一个释放内存的函数

void freeMaze(Maze *maze) {

for(int i = 0; i < maze->height; i++) {

free(maze->map[i]);

}

free(maze->map);

free(maze);

}

4.在遍历图像的过程中我们使用深度优先搜索的方式(dfs),我们在遍历的过程中

我们需要判断某个坐标是否可以通过如果不可以通过我们就不能访问这个坐标

int isValid(Maze *maze, int x, int y) {

return x >= 0 && x < maze->width && y >= 0 && y < maze->height && maze->map[y][x] != 1;

}

如果超过了地图范围或者是墙壁的情况下我们返回-1,(因为我们先给高度分配的内存然后给宽度分配的内存,所以我们坐标是y,x)

5.之后我们还需要一个深度优先搜索的函数,dfs,函数需要的参数有地图maze,以及坐标下,

y

void dfs(Maze *maze, int x, int y) {

在dfs函数中我们先判断如果坐标是无效的情况下或者已经访问过了的话我们不重复访问,(因为如果之前已经对这个坐标使用过dfs函数了,没有必要再重复一次)

if(!isValid(maze, x, y) || maze->map[y][x] == 2) return;因为我们采取标记地图的方式所以不需要返回任何数据

如果程序可以继续进行证明这是一个没有访问过的且有效的坐标

我们先判断一下是否到达了终点,如果到达终点我们将终点标记为已经访问过,然后返回

将reachend设置为true(可以到达终点的我们不设置成陷阱)

if(x == maze->width - 1 && y == maze->height - 1) {

maze->map[y][x] = 2;

maze->reachend = true;

return;

}

如果程序进行到这里证明我们访问了一个不是终点的并且有效的坐标,我们有可能在去往终点的路上,或者我们有可能进入了陷阱(但是不可能是不可达的因为我们已经到达了)

所以我们标记当前方格为已访问

maze->map[y][x] = 2;

然后我们从这个方格调用dfs函数,向右走、向上走,如果找到无效方格或者找到已经访问过的方格我们会返回,如果找到终点我们会返回,如果找到的方格是有效的,并且没有访问过,而且也不是终点,但是没有返回,证明从这个方格无法到达终点,那么我们将这个方格标记为3,陷阱方格

dfs(maze, x, y + 1);

dfs(maze ,x + 1, y);

// 如果没有没有返回我们认为不可以到达终点,那么我们标记为陷阱

if(!(maze->reachend) && (maze->map[y][x] == 2)) {

maze->map[y][x] = 3;

maze->trapCount++;

}

}

6.我们还需要一个函数用来计算不可达的方格数量(整个迷宫使用dfs遍历过之后还没有被标记为1墙壁、2已访问、3陷阱)的方格也就是说还是0的方格是不可达方格

void countUnreachable(Maze *maze) {

for(int i = 0; i < maze->height; i++){

for(int j = 0; j < maze->width; j++) {

if(maze->map[i][j] == 0) {

maze->unreachableCount++;

}

}

}

}

7.然后是主函数

int main() {

我们首先定义变量读取输入中的数据

int width, height;

scanf("%d %d", &width, &height);

然后初始化迷宫

Maze *maze = createMaze(width, height);

读取墙壁并在迷宫map上标记

首先读取墙壁数目

int wallCount;

scanf("%d", &wallCount);

for(int i = 0; i < wallCount; i++) {

int x, y;

scanf("%d %d", &x, &y);

maze->map[y][x] = 1;

}

然后我们从原点开始进行深度优先搜索

dfs(maze, 0 , 0);

然后我们计算不可达方格数量

countUnreachable(maze);

然后我们输出陷阱和不可达方格的数量

printf("%d %d\n", maze->trapCount, maze->unreachableCount);

最后别忘了释放内存

freeMaze(maze);

return 0;

}

三、具体步骤

使用的语言是C

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>typedef struct {int width;int height;int** map;int trapCount;int unreachableCount;bool reachEnd;
} Maze;Maze* createMaze(int width, int height) {Maze* maze = (Maze*)malloc(sizeof(Maze));maze->width = width;maze->height = height;maze->trapCount = 0;maze->unreachableCount = 0;maze->map = (int**)malloc(height * sizeof(int*));for (int i = 0; i < height; i++) {maze->map[i] = (int*)malloc(width * sizeof(int));for (int j = 0; j < width; j++) {maze->map[i][j] = 0; // 0表示还没有访问过}}maze->reachEnd = false;return maze;
}void freeMaze(Maze* maze) {for (int i = 0; i < maze->height; i++) {free(maze->map[i]);}free(maze->map);free(maze);
}void printMaze(Maze* maze) {for (int i = maze->height - 1; i >= 0; i--) {for (int j = 0; j < maze->width; j++) {printf("%d ", maze->map[i][j]);}printf("\n");}
}bool isValid(Maze* maze, int x, int y) {if (x < 0 || y < 0 || x >= maze->width || y >= maze->height ||maze->map[y][x] == 1) {return false;}return true;
}void dfs(Maze* maze, int x, int y) {// printf("x is %d y is %d end is %d , %d\n", y, x, maze->height - 1, maze->width - 1);if (!isValid(maze, x, y) || maze->map[y][x] == 2) return;if (y == maze->height - 1 && x == maze->width - 1) {// printf("reach end\n");maze->map[y][x] = 2;maze->reachEnd = true;return;}if (maze->map[y][x] == 0) {maze->map[y][x] = 2;}dfs(maze, x + 1, y);dfs(maze, x, y + 1);// 如果没有到达终点,并且已经访问过了if (!(maze->reachEnd) && (maze->map[y][x] == 2)) {maze->map[y][x] = 3; // 3表示是陷阱maze->trapCount++;}// printMaze(maze);// printf("\n");
}void countUnreachable(Maze* maze) {for (int i = 0; i < maze->height; i++) {for (int j = 0; j < maze->width; j++) {if (maze->map[i][j] == 0) maze->unreachableCount++;}}
}int main() {int width, height;scanf("%d %d", &width, &height);Maze* maze = createMaze(width, height);int wallCount;scanf("%d", &wallCount);for (int i = 0; i < wallCount; i++) {int x, y;scanf("%d %d", &x, &y);maze->map[y][x] = 1;// 1表示墙壁,因为我们先设置的高度然后设置的宽度,所以是y,x}// maze->map[0][0] = 5;// maze->map[maze->height - 1][maze->width - 1] = 6;// printMaze(maze);dfs(maze, 0, 0);countUnreachable(maze);printf("%d %d\n", maze->trapCount, maze->unreachableCount);// printMaze(maze);free(maze);return 0;
}

http://www.ppmy.cn/embedded/149745.html

相关文章

yarn list --pattern vuex-module-decorators

dgqdgqdeMac-mini spid-admin % yarn list --pattern vuex-module-decorators yarn list v1.22.22 └─ vuex-module-decorators0.16.1 ✨ Done in 0.24s.好的&#xff0c;这段代码是一个典型的 Vuex 模块定义&#xff0c;使用了 vuex-module-decorators 库。这个库为 Vuex 提…

爬虫入门二 beautifulsoup

1 beautifulsoup简介 BeautifulSoup 是一个可以从HTML或XML文件中提取数据的Python库.它能够通过转换器实现文档导航、查找、修改。 pip install beautifulsoup4http://beautifulsoup.readthedocs.io/zh_CN/latest/ 2 前端知识 w3school 在线教程 HTTP:HyperText Markup La…

互联网路由架构

大家觉得有意义和帮助记得及时关注和点赞!!! 本书致力于解决实际问题&#xff0c;书中包含大量的架构图、拓扑图和真实场景示例&#xff0c;内容全面 且易于上手&#xff0c;是不可多得的良心之作。本书目的是使读者成为将自有网络集成到全球互联网 领域的专家。 以下是笔记内…

基于JAVA+SpringBoot+Vue的影院订票系统

基于JAVASpringBootVue的影院订票系统 前言 ✌全网粉丝20W,csdn特邀作者、博客专家、CSDN[新星计划]导师、java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末附源码下载链接&#x1f345; 哈喽兄…

【HarmonyOS之旅】ArkTS语法(二)->动态构建UI元素

目录 1 -> Builder 2 -> BuilderParam8 2.1 -> 引入动机 2.2 -> 参数初始化组件 2.3 -> 尾随闭包初始化组件 3 -> Styles 4 -> Extend 5 -> CustomDialog 1 -> Builder 可通过Builder装饰器进行描述&#xff0c;该装饰器可以修饰一个函数&…

网络技术-QoS技术在网络中的位置

QoS技术包括流分类、流量监管、流量整形、限速、拥塞管理、拥塞避免等。下面对常用的技术进行简单地介绍。 如图&#xff0c;常用QoS技术在网络中的位置 如上图所示&#xff0c;流分类、流量监管、流量整形、拥塞管理和拥塞避免主要完成如下功能&#xff1a; 流分类&#xf…

Configfs - 用户空间驱动的内核对象配置

什么是configfs configfs 是一个基于 RAM 的文件系统&#xff0c;提供与 sysfs 相反的功能。sysfs 是一个基于文件系统的内核对象视图&#xff0c;而 configfs 是一个基于文件系统的内核对象管理器&#xff0c;即 config_items。 使用 sysfs&#xff0c;可以在内核中创建一个…

使用 VSCode 学习与实践 LaTeX:从插件安装到排版技巧

文章目录 背景介绍编辑器编译文件指定输出文件夹 usepackagelatex 语法列表插入图片添加参考文献 背景介绍 最近在写文章&#xff0c;更喜欢latex的论文引用。然后开始学习 latex。 编辑器 本文选择vscode作为编辑器&#xff0c;当然大家也可以尝试overleaf。 overleaf 有网…