蓝桥杯刷题冲刺 | 倒计时21天

作者:指针不指南吗
专栏:蓝桥杯倒计时冲刺

🐾马上就要蓝桥杯了,最后的这几天尤为重要,不可懈怠哦🐾

文章目录

  • 1.迷宫

1.迷宫

  • 题目

    链接: 迷宫 - 蓝桥云课 (lanqiao.cn)

    本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。

    下图给出了一个迷宫的平面图,其中标记为 1 的为障碍,标记为 0 的为可以通行的地方。

    010000
    000100
    001001
    110000
    

    迷宫的入口为左上角,出口为右下角,在迷宫中,只能从一个位置走到这 个它的上、下、左、右四个方向之一。

    对于上面的迷宫,从入口开始,可以按 DRRURRDDDR 的顺序通过迷宫, 一共 10 步。其中DULR 分别表示向下、向上、向左、向右走。 对于下面这个更复杂的迷宫(30 行 50 列),请找出一种通过迷宫的方式,其使用的步数最少,在步数最少的前提下,请找出字典序最小的一个作为答案。

    请注意在字典序中 D<L<R<U

    01010101001011001001010110010110100100001000101010
    00001000100000101010010000100000001001100110100101
    01111011010010001000001101001011100011000000010000
    01000000001010100011010000101000001010101011001011
    00011111000000101000010010100010100000101100000000
    11001000110101000010101100011010011010101011110111
    00011011010101001001001010000001000101001110000000
    10100000101000100110101010111110011000010000111010
    00111000001010100001100010000001000101001100001001
    11000110100001110010001001010101010101010001101000
    00010000100100000101001010101110100010101010000101
    11100100101001001000010000010101010100100100010100
    00000010000000101011001111010001100000101010100011
    10101010011100001000011000010110011110110100001000
    10101010100001101010100101000010100000111011101001
    10000000101100010000101100101101001011100000000100
    10101001000000010100100001000100000100011110101001
    00101001010101101001010100011010101101110000110101
    11001010000100001100000010100101000001000111000010
    00001000110000110101101000000100101001001000011101
    10100101000101000000001110110010110101101010100001
    00101000010000110101010000100010001001000100010101
    10100001000110010001000010101001010101011111010010
    00000100101000000110010100101001000001000000000010
    11010000001001110111001001000011101001011011101000
    00000110100010001000100000001000011101000000110011
    10101000101000100010001111100010101001010000001000
    10000010100101001010110000000100101010001011101000
    00111100001000010000000110111000000001000000001011
    10000001100111010111010001000110111010101101111000
    
  • 第一次

    #include<bits/stdc++.h>
    using namespace std;
    
    typedef pair<int,int> PII;
    
    const int N=40,M=60;
    int n=30,m=40;
    char g[N][M];
    char path[N*M];
    bool st[N][M];
    int d;
    
    void bfs()
    {
    	int u=0;
    	
    	char c[4]={'D','L','R','U'};
    	int dx[4]={0,-1,1,0},dy[4]={1,0,0,-1};
    	
    	queue<PII> q;
    	q.push({0,0});
    	
    	while(!q.empty())
    	{
    		auto t=q.front();
    		q.pop();
    		
    		for(int i=0;i<4;i++)
    		{
    			int x=t.first+dx[i],y=t.second+dy[i];
    			if(!st[x][y]&&x>=0&&x<n&&y<m&&y>=0&&g[x][y]=='0')
    			{
    				d++;
    				
    				st[x][y]=true;
    				q.push({x,y}); 
    				path[u++]=c[i];
    				
    				if(x==n-1&&y==m-1) 
    				{
    					for(int k=0;k<d;k++)
    						cout<<path[k];
    					return ;
    				}
    			} //只能保证它可以走到终点,但可能不是最短
    		}
    	}
    }
    
    int main()
    {
    	for(int i=0;i<n;i++)
    		for(int j=0;j<m;j++)
    			cin>>g[i][j];
    	
    	bfs();
    
    	return 0;
    }
    

    没有输出,有几天没有写 bfs ,好多细节都忘记了

  • 正确题解

    #include <iostream>
    #include <algorithm>
    #include <string>
    #include <string.h>
    #include <queue>
    using namespace std;
    char a[40][60];                                                 //存图
    int nextx[4] = { 1,0,0,-1 }, nexty[4] = { 0,-1,1,0 };           //D<L<R<U      字典序直接把方向数组处理好就可以了
    int dist[40][60];                                               //定义一个dist数组,用来存放各点到终点的最短距离
    char dir[4] = { 'D','L','R','U' };                             
    bool check(int x, int y) {
        return x > 0 && y > 0 && x <= 30 && y <= 50 && a[x][y] == '0'&&dist[x][y] == -1;
    }
    void bfs() {                                                    //BFS扫一遍,求出各点到终点的最短距离
        queue<pair<int, int> >q;
        memset(dist, -1, sizeof(dist));
        dist[30][50] = 0;
        q.push({ 30,50 });
        while (!q.empty()) {
            pair<int ,int> t = q.front();
            q.pop();
     
            for (int i = 0; i < 4; i++) {
                int newx = t.first + nextx[i];
                int newy = t.second + nexty[i];
                if (check(newx, newy)) {
                    dist[newx][newy] = dist[t.first][t.second] + 1;
                    q.push({ newx,newy });
                }
            }
     
        }
    }
     
    int main() {
     
        for (int i = 1; i <= 30; i++)
            for (int j = 1; j <= 50; j++)
                cin >> a[i][j];
        bfs();
     
        int x = 1, y = 1;                                                                       //从起点开始遍历
        string res;                                                                             //存答案
        while (x != 30 || y != 50) {
            for (int i = 0; i < 4; i++) {
                int newx = x + nextx[i];
                int newy = y + nexty[i];
                if (newx > 0 && newy > 0 && newx <= 30 && newy <= 50 && a[newx][newy] == '0'&&dist[newx][newy]==dist[x][y]-1) {  //这个判断真是妙啊
                    x = newx, y = newy;
                    res += dir[i];
                    break;
                }
            }
        }
        cout << res << "\n";
        return 0;
    }
    
  • 反思

    1. dx , dy 的坐标,向下为 正
    2. bfs 存路径,正着存的话,会有很多路径,无法确定最优解;所以只能倒着存,可以记录子节点是怎么转移过来的,我的写错了
      Alt

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Three.js——learn02

Three.js——learn02Three.js——learn02通过轨道控制器查看物体OrbitControls核心代码index2.htmlindex.cssindex2.jsresult添加辅助器1.坐标轴辅助器AxesHelper核心代码完整代码2.箭头辅助器ArrowHelper核心代码完整代码3.相机视锥体辅助器CameraHelper核心代码完整代码Three…

近期投简历、找日常实习的一些碎碎念(大二---测试岗)

嘿嘿嘿&#xff0c;我又回来了&#xff0c;相信不少兄弟已经发现我似乎已经断更了好久&#xff0c;哈哈&#xff0c;我是尝试去找实习&#xff0c;投简历面试去了。 先说一下背景。 目录 背景 求职进行中 简历 投递和沟通 收获和感受 背景 博主&#xff0c;大二软件工程…

Arthas工具的基本使用

介绍 Arthas 是Alibaba开源的Java诊断工具&#xff0c;深受开发者喜爱。在线排查问题&#xff0c;无需重启&#xff1b;动态跟踪Java代码&#xff1b;实时监控JVM状态。Arthas支持JDK 6&#xff0c;支持Linux/Mac/Windows&#xff0c;采用命令行交互模式&#xff0c;同时提供丰…

Python截图自动化工具

1、展示部分源码(写的比较乱&#xff0c;哈哈) 2、功能展示 1&#xff09;首页 2&#xff09;按钮截图(用于自动翻页) 3&#xff09;保存位置按钮(选择图片保存的位置) 4&#xff09;重复次数&#xff0c;就是要截取多少次 5&#xff09;定位截屏(截取的内容&#x…

[数据分析与可视化] Python绘制数据地图1-GeoPandas入门指北

本文主要介绍GeoPandas的基本使用方法&#xff0c;以绘制简单的地图。GeoPandas是一个Python开源项目&#xff0c;旨在提供丰富而简单的地理空间数据处理接口。GeoPandas扩展了Pandas的数据类型&#xff0c;并使用matplotlib进行绘图。GeoPandas官方仓库地址为&#xff1a;GeoP…

尚融宝06-ECMAScript基本介绍和使用

目录 一、ECMAScript 1、ECMA 2、ECMAScript 3、什么是 ECMA-262 4、ECMA-262 历史 5、ECMAScript 和 JavaScript 的关系 二、基本语法 1、let声明变量 2、const声明常量 3、解构赋值 4、模板字符串 5、声明对象简写 6、定义方法简写 7、参数的默认值 8、对象拓…

QT常用位置函数区别

目录1、引言2、实验代码3、位置函数3.1 x()3.2 y()3.3 frame()3.4 pos()3.5 geometry()3.6 width()3.7 height()3.8 rect()3.9 size()1、引言 QT有众多图形绘制函数&#xff0c;包括x()、y()、frame()、pos()、geometry()、width()、height()、rect()、size()&#xff0c;它们…

【Java学习笔记】多线程与线程池

多线程与线程池一、多线程安全与应用1、程序、进程与线程的关系2、创建多线程的三种方式&#xff08;1&#xff09;继承Thread类创建线程【不推荐】&#xff08;2&#xff09;实现Runnable接口创建线程&#xff08;3&#xff09;Callable接口创建线程3、线程的生命周期4、初识线…

基础入门 HTTP数据包Postman构造请求方法请求头修改状态码判断

文章目录数据-方法&头部&状态码请求requestResponse状态码案例-文件探针&登录爆破工具-Postman自构造使用数据-方法&头部&状态码 请求request 1、常规请求-Get 2、用户登录-Post •get&#xff1a;向特定资源发出请求&#xff08;请求指定页面信息&#x…

为什么这么NB?huatuo革命Unity热更新

最近huatuo(华佗)热更新解决方案火爆了unity开发圈,起初我觉得热更新嘛&#xff0c;不就是内置一个脚本解释器脚本语言开发&#xff0c;如xLua, ILRuntime, puerts。Huatuo又能玩出什么花样&#xff0c;凭什么会这么NB&#xff0c;引起了那么多程序员的关注与称赞呢&#xff1f…

单片机——IIC协议与24C02

1、基础知识 1.1、IIC串行总线的组成及工作原理 I2C总线只有两根双向信号线。一根是数据线SDA&#xff0c;另一根是时钟线SCL。 1.2、I2C总线的数据传输 I2C总线进行数据传送时&#xff0c;时钟信号为高电平期间&#xff0c;数据线上的数据必须保持稳定&#xff0c;只有在时钟…

Linux实操之进程管理

文章目录一、基本介绍二、显示系统执行的进程基本介绍三、ps详解四、终止进程kill和killall介绍:●基本语法常用选项五、查看进程树pstree基本语法常用选项一、基本介绍 1&#xff0e;在LINUX中&#xff0c;每个执行的程序都称为一个进程。每一个进程都分配一个ID号(pid,进程号…

【SCL】实现简单算法--冒泡排序

使用SCL语言实现一个冒泡排序的简单算法 文章目录 目录 文章目录 前言 二、实现排序 1.读取存储器地址&#xff08;PEEK&#xff09;指令 2.编写程序 总结 前言 本文我们来一起使用SCL来实现一个简单的算法——冒泡排序&#xff1b;它可以对少量数据进行从小到大或从大到小排序…

【Linux】GDB的安装与使用

安装安装gdb的具体步骤如下&#xff1a;1、查看当前gdb安装情况rpm -qa | grep gdb如果有&#xff0c;则可以先删除&#xff1a;rpm -e --nodeps 文件名如果没有&#xff0c;则进行下一步。2、下载gdb源码包或者直接apt安装。apt命令安装&#xff1a;sudo apt install gdb源码包…

Qt之QPainter绘制多个矩形/圆形(含源码+注释)

一、绘制示例图 下图绘制的是矩形对象&#xff0c;但是将绘制矩形函数&#xff08;drawRect&#xff09;更改为绘制圆形&#xff08;drawEllipse&#xff09;即可绘制圆形。 二、思路解释 绘制矩形需要自然要获取矩形数据&#xff0c;因此通过鼠标事件获取每个矩形的rect数…

一个完整的渗透学习路线是怎样的?如何成为安全渗透工程师?

前言 1/我是如何学习黑客和渗透&#xff1f; 我是如何学习黑客和渗透测试的&#xff0c;在这里&#xff0c;我就把我的学习路线写一下&#xff0c;让新手和小白们不再迷茫&#xff0c;少走弯路&#xff0c;拒绝时间上的浪费&#xff01; 2/学习常见渗透工具的使用 注意&…

SpringBoot集成 SpringSecurity安全框架

文章目录一、CSRF跨站请求伪造攻击二、项目准备三、认识 SpringSecurity3.1 认证&#x1f380;①直接认证&#x1f380;②使用数据库认证3.2 授权&#x1f361;①基于角色授权&#x1f361;②基于权限的授权&#x1f361;③使用注解判断权限3.3 "记住我"3.4 登录和注…

【JavaEE】如何将JavaWeb项目部署到Linux云服务器?

写在前面 大家好&#xff0c;我是黄小黄。不久前&#xff0c;我们基于 servlet 和 jdbc 完善了博客系统。本文将以该系统为例&#xff0c;演示如何将博客系统部署到 Linux 云服务器。 博客系统传送门&#xff1a; 【JavaEE】前后端分离实现博客系统&#xff08;页面构建&#…

arcpy基础篇(3)-处理空间数据

ArcPy的数据访问模块arcpy.da&#xff0c;可以控制会话、编辑操作、游标、表或要素类与NumPy数组之间相互转换的函数以及对版本化和复本工作流的支持。 1.使用游标访问数据 游标是一个数据库术语&#xff0c;它主要用于访问表格中的每一行记录或者向表中插入新的记录。在ArcG…

【数据结构】Java实现单链表

目录 1. ArrayList的缺陷 2. 链表 2.1 链表的概念及结构 2.2 接口的实现 3. 动手实现单链表 3.1 重写SeqList接口方法 3.2 在当前链表头部添加节点&#xff08;头插&#xff09; 3.3 在 第index位置添加节点&#xff08;任意位置&#xff09; 3.4 在当前链表尾部添加…
最新文章