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

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

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

文章目录

  • 0.知识点
  • 1.乳草的入侵

今天写 搜索题

0.知识点

  • DFS

    • 设计步骤
    1. 确定该题目的状态(包括边界)
    2. 找到状态转移方式
    3. 找到问题的出口、计数或者某一个状态
    4. 设计搜索
    • 代码模板
    ans  //答案,用全局变量来表示
    
    bool st[N]; //标记状态
        
    bool check(参数)
    {
    	if(满足条件)
            return 1;
        return 0;
    }
    
    void dfs(int step)
    {
    	if(判断边界)
        {
    		不在边界内,即回溯
        }
        尝试每一种可能  //for 循环
        {
    		满足check条件//if
            标记 //  bool st[]
            继续下一步 dfs(step+1)
            恢复初始状态(回溯的时候要用到)
        }
        
    }
    
  • BFS

    • 前引

      一般使用队列来实现;

      BFS一般用于求最短路问题,边权为1

    • 步骤设计

      1. 确定该题目的状态(包括边界)
      2. 找到状态转移方式
      3. 找到问题的出口,计数或者某一个状态
      4. 设计搜索

      和前面的差不多,一般情况下,BFS 和 DFS 可以互换

    • 注意

      1. BFS=队列
      2. BFS:逐层扩展下一层,把扩展出的下一层状态放进队列中处理
      3. 如果这些状态有相同的,只需要搜一次,只需要进入队列一次
      4. 必须判重

1.乳草的入侵

  • 题目

    链接: 189. 乳草的入侵 - AcWing题库

    农民约翰一直努力让他的草地充满鲜美多汁而又健康的牧草。

    可惜天不从人愿,他在植物大战人类中败下阵来。

    邪恶的乳草已经在他的农场的西北部份占领了一片立足之地。

    草地像往常一样,被分割成一个高度为 Y,宽度为 X 的直角网格。

    (1,1)是左下角的格(也就是说坐标排布跟一般的 X,Y 坐标相同)。

    乳草一开始占领了格 (Mx,My)。

    每个星期,乳草传播到已被乳草占领的格子四面八方的每一个没有很多石头的格(包括垂直与水平相邻的和对角线上相邻的格)内。

    1 周之后,这些新占领的格又可以把乳草传播到更多的格里面了。

    达达想要在草地被乳草完全占领之前尽可能的享用所有的牧草。

    她很好奇到底乳草要多久才能占领整个草地。

    如果乳草在 0 时刻处于格 (Mx,My),那么几个星期以后它们可以完全占领入侵整片草地呢(对给定的数据总是会发生)?

    在草地地图中,. 表示草,而 * 表示大石。

    比如这个 X=4,Y=3 的例子。

    ....
    ..*.
    .**.
    

    如果乳草一开始在左下角(第 1 排,第 1 列),那么草地的地图将会以如下态势发展:

          ....  ....  MMM.  MMMM  MMMM  
          ..*.  MM*.  MM*.  MM*M  MM*M  
          M**.  M**.  M**.  M**.  M**M  
    星期数  0     1     2     3     4
    

    乳草会在 4 星期后占领整片土地。

    输入格式

    第 1 行: 四个由空格隔开的整数: X, Y, Mx, My

    第 2 到第 Y+1 行: 每行包含一个由 X 个字符(. 表示草地,* 表示大石)构成的字符串,共同描绘了草地的完整地图。

    输出格式

    输出一个整数,表示乳草完全占领草地所需要的星期数。

    数据范围

    1≤X,Y≤100

    输入样例:

    4 3 1 1
    ....
    ..*.
    .**.
    

    输出样例:

    4
    
  • 前n次 AC 0%

    #include<bits/stdc++.h>
    using namespace std;
    
    typedef pair<int,int> PII;
    
    const int N=110;
    
    int n,m,a,b;
    
    char g[N][N];
    int d[N][N];
    
    int dx[8]={0,0,-1,1,-1,1,-1,1},dy[8]={1,-1,0,0,1,1,-1,-1};
    
    bool check()  //判断是否满足条件,除了石头都是乳草
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(g[i][j]=='.')
                    return false;
        return true;
    }
    
    void f()  //输出调式用的
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cout<<g[i][j];
            }
            cout<<endl;
        }
        cout<<endl;
    }
    
    void bfs()
    {
        memset(d,-1,sizeof d);  //初始化
        
        int cnt=0;  //扩展的次数
        
        queue<PII> q;
        q.push({m-b+1,a});
        
        d[m-b+1][a]=0;
        
        //下面几乎全错,没想出来怎么一次性扩展一层
        while(q.size())
        {
            auto t=q.front();
            q.pop();
            int flag=0;
            for(int i=0;i<8;i++)
            {
                
                int x=t.first+dx[i],y=t.second+dy[i];
                if(d[x][y]==-1&&x>=1&&y>=1&&x<=n&&y<=m&&g[x][y]!='*')
                {
                    flag=1;
                    q.push({x,y});
                    d[x][y]=d[t.first][t.second]+1;
                    g[x][y]='M';
                    
                }
                if(flag) cnt++;
                if(check())
                    {
                        cout<<cnt;
                        return ;
                    }
            }
        }
        
    }
    
    int main()
    {
        cin>>n>>m>>a>>b;
        
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>g[i][j];  //看题,起点应该从1开始,存图
                
        g[m-b+1][a]='M';  //地图的坐标 (1,1)在右下角,(a,b)在二维数组里面的表示,在纸上举个例子,模拟一下,硬想我是真不行
        
        bfs();
        
        return 0;
    }
    
  • 模仿正确的题解写的 AC 0%

    #include<bits/stdc++.h>
    using namespace std;
    
    typedef pair<int,int> PII;
    
    const int N=110;
    
    int n,m;
    int ans,cnt;
    PII st;
    char g[N][N];
    int d[N][N],vis[N][N];
    int dx[8]= {1,-1,0,0,1,-1,1,-1}, dy[8]= {0,0,1,-1,1,-1,-1,1};
    
    void bfs()
    {
        queue<PII> q;
        q.push(st);
        
        d[st.first][st.second]=0;
        vis[st.first][st.second]=1;
        
        while(q.size())
        {
            auto t=q.front();
            q.pop();
            
            for(int i=0;i<8;i++)
            {
                int x=st.first+dx[i],y=st.second+dy[i];
                if(!vis[x][y]&&x>=1&&x<=n&&y>=1&&y<=m&&g[x][y]!='*')
                {
                    cnt--;
                    vis[x][y]=1;
                    q.push({x,y});
                    d[x][y]=d[t.first][t.second]+1;
                    ans=max(ans,d[x][y]);
                    if(cnt==0) 
                        return ;
                }
            }
        }
    }
    
    
    int main()
    {
        scanf("%d%d%d%d\n",&n,&m,&st.second,&st.first);
        
        
        for(int i=n;i>=1;i--)
            for(int j=1;j<=m;j++)
            {
                cin>>g[i][j];
                if(g[i][j]=='.')
                    cnt++;
            }
            
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            cout<<g[i][j];
            cout<<endl;
            
        if(g[st.first][st.second]=='.') 
            cnt--;
        
        bfs();
        
        cout<<ans;
        
        return 0;
    }
    

    不知道哪错了 Debug 中

  • 正确代码

    #include <bits/stdc++.h>
    using namespace std;
    #define fir(i,a,b) for(int i=a;i<=b;i++)
    #define pii pair<int,int>
    #define mk(a,b) make_pair(a,b)
    const int dx[8]= {1,-1,0,0,1,-1,1,-1};
    const int dy[8]= {0,0,1,-1,1,-1,-1,1};
    const int N=110;
    pii st,now;
    char s[N][N];
    int cnt,n,m,vis[N][N],ans,dis[N][N];
    queue<pii> q;
    int check(int x,int y)//判断:在范围;没有被访问过;不是石头
    {
        return x>=1 && x<=n && y>=1 && y<=m && vis[x][y]==0 && s[x][y]!='*';
    }
    int bfs()
    {
        q.push(st);
        dis[st.first][st.second]=0;
        vis[st.first][st.second]=1;
        while(q.size())
        {
            now=q.front();
            q.pop();
            fir(i,0,7)
            {
                int x=now.first+dx[i],y=now.second+dy[i];//拓展
                if (check(x,y))
                {
                    cnt--;
                    vis[x][y]=1;
                    dis[x][y]=dis[now.first][now.second]+1;
                    ans=max(ans,dis[x][y]);//找出最大的dis,也就是最后答案
                    q.push(mk(x,y));
                    if (cnt==0)//所有的草地被占满了.
                        return 1;
                }
            }
        }
    }
    int main()
    {
        scanf("%d%d%d%d\n",&m,&n,&st.second,&st.first);//读入真是博大精深啊!!!!!
        for(int i=n; i>=1; i--)
        {
            for(int j=1; j<=m; j++)
            {
                s[i][j]=getchar();
                if (s[i][j]=='.')
                    cnt++;//统计有多少个空
            }
            getchar();
        }
        if (s[st.first][st.second]=='.')//刚开始就有一根乳草.
            cnt--;
        bfs();
        cout<<ans;
    }
    
  • 反思

    今天晚上没课,四个小时就做这个题,最后还没做出来

    • 往外扩展几层,直接就是 最短距离 d[x]

    最大的收获就是 (1,1)在左下角的坐标的表示,详细看代码

    • 中间有一次,考虑这个问题,但只是仅仅想到一个起始点的坐标,没考虑全面,整个数组都是

    今天的时间真的浪费掉了,应该及时看题解的

Alt

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

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

相关文章

串口,IIC,SPI,USB等总线硬件知识总结

串口&#xff0c;IIC&#xff0c;SPI&#xff0c;USB等总线硬件知识总结 文章目录串口&#xff0c;IIC&#xff0c;SPI&#xff0c;USB等总线硬件知识总结1 串口2.I2C3.SPI4.USB控制&#xff08;Control&#xff09;传输方式同步&#xff08;Isochronous&#xff09;传输方式中…

vue3+vite+ts 搭建脚手架01创建vite项目并且在项目中初次使用router

vue3vite 搭建脚手架01创建vite项目并且在项目中使用router 1.使用yarn安装vite项目 yarn create vite 搭建vite项目 在开发语言中选择vuets2.安装现在最新的 vue-router4 yarn add vue-router4 在packger中检查是否成功安装3.简单配置router文件 在项目中新建views和…

【C++】map、set、multimap、multiset的介绍和使用

我讨厌世俗&#xff0c;也耐得住孤独。 文章目录一、键值对二、树形结构的关联式容器1.set1.1 set的介绍1.2 set的使用1.3 multiset的使用2.map2.1 map的介绍2.2 map的使用2.3 multimap的使用三、两道OJ题1.前K个高频单词&#xff08;less<T>小于号是小的在左面升序&…

如何将字符串反转?

参考答案 使用 StringBuilder 或 StringBuffer 的 reverse 方法&#xff0c;本质都调用了它们的父类 AbstractStringBuilder 的 reverse 方法实现。&#xff08;JDK1.8&#xff09;不考虑字符串中的字符是否是 Unicode 编码&#xff0c;自己实现。递归1. public AbstractStrin…

优秀程序员的5个特征,你在第几层?

每个人程序员都对未来的职业发展有着憧憬和规划&#xff0c;要做架构师、要做技术总监、要做CTO。但现实总是复杂的&#xff0c;日复一日的工作与生活总能让人一次又一次地陷入迷茫。大部分原因就是对职业发展轨迹和自我能力提升的一般规律缺乏认识&#xff0c;做事找不到方向或…

WebSocket 测试工具

一、WebSocket 简介 WebSocket是一种在单个TCP连接上进行全双工通信的协议。 WebSocket使得客户端和服务器之间的数据交换变得更加简单&#xff0c;允许服务端主动向客户端推送数据。在WebSocket API中&#xff0c;浏览器和服务器只需要完成一次握手&#xff0c;两者之间就直…

MySQL数据库管理系统安装部署——Linux

MySQL数据库管理系统安装部署——Linux 简介 MySQL数据库管理系统&#xff08;后续简称MySQL)&#xff0c;是一款知名的数据库系统&#xff0c;其特点是:轻量、简单、功能丰富。MySQL数据库可谓是软件行业的明星产品&#xff0c;无论是后端开发、大数据、AI、运维、测试等各类…

linux入门---操作体统的概念

什么是操作系统 操作系统是一个对软硬件资源进行管理的软件。计算机由一堆硬件组成&#xff0c;这些硬件遵循着冯诺依曼体系结构 在这个硬件的基础上还有一个软件叫做操作系统 操作系统的任务是对硬件进行管理&#xff0c;既然是管理的话操作系统得访问到底层的硬件&#xf…

【贪心算法】一文让你学会“贪心”(贪心算法详解及经典案例)

文章目录前言如何理解“贪心算法”&#xff1f;贪心算法实战分析1.分糖果2.钱币找零3.区间覆盖内容小结最后说一句&#x1f431;‍&#x1f409;作者简介&#xff1a;大家好&#xff0c;我是黑洞晓威&#xff0c;一名大二学生&#xff0c;希望和大家一起进步。 &#x1f47f;本…

Spring Boot 各层作用与联系

目录 1 Entity 层 2 DAO 层 3 Service 层 4 Controller 层 Spring Boot 各层之间的联系&#xff1a; controller 层-----> service 层(接口->接口实现类) -----> dao 层的.mapper 文件 -----> 和 mapper 层里的.xml 文件对应 1 Entity 层 实体层&#xff0c;…

Java笔记_6(面向对象)

Java笔记_6一、面向对象1.1、设计对象并使用1.2、封装1.3、就近原则和this关键字1.4、构造方法1.5、标准的JavaBean类1.6、对象内存图1.7、基本数据类型和引用数据类型1.8、this的内存原理1.9、成员和局部二、面向对象&#xff08;综合练习&#xff09;2.1、文字版格斗游戏2.2、…

正式环境关闭swagger

直接上步骤&#xff0c;如图&#xff1a;1&#xff0c;启动判断写在相应的环境配置文件中&#xff0c;根据条件判断是否启动 swagger &#xff1a;添加配置项&#xff1a;swagger.is.enable配置文件中添加&#xff1a;#是否激活 swagger true or falseswagger.is.enabletrue2&a…

【Linux】-初识Linux

作者&#xff1a;学Java的冬瓜 博客主页&#xff1a;☀冬瓜的主页&#x1f319; 专栏&#xff1a;【Linux】 分享&#xff1a;逆着光行走&#xff0c;任风吹雨打。 ——《起风了》 主要内容&#xff1a;Linux的一些最基本指令&#xff0c;Linux的小程序&#xff0c;Linux关于连…

从暴力递归到动态规划(2)小乖,你也在为转移方程而烦恼吗?

前引&#xff1a;继上篇我们讲到暴力递归的过程&#xff0c;这一篇blog我们将继续对从暴力递归到动态规划的实现过程&#xff0c;与上篇类似&#xff0c;我们依然采用题目的方式对其转化过程进行论述。上篇博客&#xff1a;https://blog.csdn.net/m0_65431718/article/details/…

看完这篇 教你玩转渗透测试靶机vulnhub——My File Server: 1

Vulnhub靶机My File Server: 1渗透测试详解Vulnhub靶机介绍&#xff1a;Vulnhub靶机下载&#xff1a;Vulnhub靶机安装&#xff1a;Vulnhub靶机漏洞详解&#xff1a;①&#xff1a;信息收集&#xff1a;②&#xff1a;FTP匿名登入&#xff1a;③&#xff1a;SMB共享服务&#xf…

【微信小程序】-- 使用 Git 管理项目(五十)

&#x1f48c; 所属专栏&#xff1a;【微信小程序开发教程】 &#x1f600; 作  者&#xff1a;我是夜阑的狗&#x1f436; &#x1f680; 个人简介&#xff1a;一个正在努力学技术的CV工程师&#xff0c;专注基础和实战分享 &#xff0c;欢迎咨询&#xff01; &…

【Docker】Compose容器编排LNMP上云

文章目录什么是Docker-Compose下载安装官网官网下载安装卸载Compose核心概念一文件两要素三个步骤Compose常用命令DjangoMysqlRedisNginx部署部署架构构建django容器 - - - dockerfile编写构建Nginx容器docker-compose 编排容器Django项目配置custom_webmysql容器redis容器Djan…

一文看懂数据仓库

数据仓库数据仓库的概念数据仓库的主要特征数据仓库的分层数据仓库的分层介绍原始数据层&#xff1a;ODS&#xff08;Operational Data Store&#xff09;数据仓库层&#xff1a;DW&#xff08;Data Warehouse&#xff09;数据明细层&#xff1a;DWD&#xff08;Data Warehouse…

邪恶的想法冒出,立马启动python实现美女通通下

前言 嗨喽~大家好呀&#xff0c;这里是魔王呐 ❤ ~! 完整源码、python资料: 点击此处跳转文末名片获取 当我在首页刷到这些的时候~ 我的心里逐渐浮现一个邪念&#xff1a;我把这些小姐姐全都采集&#xff0c;可以嘛&#xff1f; 答案当然是可以的~毕竟就我这技术&#xff0c…

【Java|golang】45. 跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说&#xff0c;如果你在 nums[i] 处&#xff0c;你可以跳转到任意 nums[i j] 处: 0 < j < nums[i] i j < n 返回到达 nums[n - 1] 的最…