【洛谷刷题】蓝桥杯专题突破-广度优先搜索-bfs（15）

戊子仲秋 2023-11-09 原文

写在前面：

怎么样才能学好一个算法？

我个人认为，系统性的刷题尤为重要，

所以，为了学好广度优先搜索，为了用好搜索应对蓝桥杯，

事不宜迟，我们即刻开始刷题！

题目：P1162 填涂颜色 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述：

输入格式：

每组测试数据第一行一个整数 n (1 ≤ n ≤ 30)。

接下来 n 行，由 0 和 1 组成的 n × n 的方阵。

方阵内只有一个闭合圈，圈内至少有一个 0。

输出格式：

已经填好数字 22 的完整方阵。

输入样例：

6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

输出样例：

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

解题思路：

这道题就是让我们将被1围起来的位置全部涂上色，

大致的思路就是：

1. 先将在外面的0用状态数组存为true

2. 而剩下位置的0，也就是需要涂色的0就都是false,

3. 完成区分后，我们就直接将需要涂色的0全部置为2即可，

另外需要注意一些特殊情况，

如果我们开始搜索的位置是1，

那就会出问题，

我们可以将这个地图外围加一圈0:

这样搜索的时候就能保证，

将所有外围的0的位置全部改变状态，

下面是代码实现：

代码：

//包好头文件
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 35;

int n;

typedef pair<int, int> PII;

bool st[N][N];
int g[N][N];
PII q[N * N];

//存偏移量
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

int head = 0;
int tail = -1;

void bfs(int x, int y)
{
    q[++tail] = {x, y};
    st[x][y] = true;
    while(head <= tail)
    {
        auto t = q[head++];
        for(int i = 0; i < 4; i++)
        {
            int a = t.first + dx[i];
            int b = t.second + dy[i];
            
            if(a < 0 || a > n + 1 || b < 0 || b > n + 1) continue;
            if(g[a][b] == 1) continue;
            if(st[a][b] == true) continue;
            
            //将在外面的位置置为true
            st[a][b] = true;
            q[++tail] = {a, b};
        }
    }
}

int main()
{
    scanf("%d", &n);
    //读入地图
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            scanf("%d", &g[i][j]);
        }
    }
    
    bfs(1, 1);
    
    //将1包围的位置置为2
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(g[i][j] == 0 && !st[i][j])
            {
                g[i][j] = 2;
            }
        }
    }
    
    //打印
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            printf("%d ", g[i][j]);
        }
        puts("");
    }
    
    return 0;
}

AC ！！！！！！！！！！

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果喜欢本文的话，欢迎点赞和评论，写下你的见解。

如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。

之后我还会输出更多高质量内容，欢迎收看。

蓝桥 bfs xff BC EF 蓝桥杯宽度优先算法

有关【洛谷刷题】蓝桥杯专题突破-广度优先搜索-bfs（15）的更多相关文章

蓝桥杯备赛（二） - 2
目录前言：一、ASC分析代码实现二、卡片分析代码实现三、直线分析代码实现四、货物摆放分析代码实现小结：前言：在刷题的过程中，发现蓝桥杯的题目和力扣的差别很大。让人有一种不一样的感觉，蓝桥杯题目偏向对于实际问题用编程去的解决，而力扣给人感觉很锻炼自己的编程思维，逻辑能力。两者结合去刷，相信会有不一样的收获。一、ASC 已知大写字母A的ASCII码为65，请问大写字母L的ASCII码是多少？分析这道题目看上去很简单，我们需确定自己计算的准确，所以我建议用编程去解决。代码实现publicclassTest8{publicstaticvoidmain(String[]args){Sy
蓝桥杯C/C++VIP试题每日一练之报时助手 - 2
?作者主页：静Yu?简介：CSDN全栈优质创作者、华为云享专家、阿里云社区博客专家，前端知识交流社区创建者?社区地址：前端知识交流社区?博主的个人博客：静Yu的个人博客?博主的个人笔记本：前端面试题个人笔记本只记录前端领域的面试题目，项目总结，面试技巧等等。接下来会更新蓝桥杯官方系统基础练习的VIP试题，依然包括解题思路，源代码等等。问题描述：给定当前的时间，请用英文的读法将它读出来。时间用时h和分m表示，在英文的读法中，读一个时间的方法是：　　如果m为0，则将时读出来，然后加上“o’clock”，如3:00读作“threeo’clock”。　　如果m不为0，则将时读出来，然后将分读出来，如5
Python学习15：恺撒密码 B（python123） - 2
描述恺撒密码是古罗马凯撒大帝用来对军事情报进行加解密的算法，它采用了替换方法对信息中的每一个英文字符循环替换为字母表序列中该字符后面的第三个字符，即，字母表的对应关系如下：‪‬‪‬‪‬‪‬‪‬‮‬‪‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‭‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‭‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬‪‬‪‬‪‬‪‬‪‬‮‬‭‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‪‬原文：ABCDEFGHIJKLMNOPQRSTUVWXYZ‪‬‪‬‪‬‪‬‪‬‮‬‪‬‫‬‪‬‪‬‪‬‪‬‪‬‮‬‪‬‭‬‪‬‪‬‪‬‪‬‪‬‮‬‫‬‮‬‪‬‪‬‪‬‪‬‪‬‮‬‭‬‫‬‪‬‪‬‪‬‪‬‪
ruby-on-rails - 在 El Capitan 上安装 Rails 时出现 -lgmp 错误的库未找到(Mac OS 10.11.1 (15B42)) - 2
在使用Rubyv2.2.2的ElCapitan(MacOSX10.11.1)上安装Rails时，出现以下错误:ERROR:Errorinstallingnokogiri:ERROR:Failedtobuildgemnativeextension./Users/jon/.rvm/rubies/ruby-2.2.2/bin/ruby-r./siteconf20151117-26799-ux15fd.rbextconf.rb--use-system-librariescheckingiftheCcompileraccepts...***extconf.rbfailed***Couldnotc
NEUQ-acm 预备队训练Week4—BFS/DFS - 2
1.深度优先搜索(DFS)深度优先遍历主要思路是从图中一个未访问的顶点V开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底…，不断递归重复此过程，直到所有的顶点都遍历完成。例题P1605迷宫题目描述给定一个N×MN\timesMN×M方格的迷宫，迷宫里有TTT处障碍，障碍处不可通过。在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。输入格式第一行为三个正整数N,M,TN,M,TN,M,T，分别表示迷宫的长宽和障碍总数。第二行为四个正整数SX,S
常见搜索模板DFS+BFS+二分搜索【算法】 - 2
本篇讲的是常见的搜索模板，搜索题的解法时比较固定的，只要把模板记熟，加上自己找几道习题练习体会后，相信各位下次遇到这类题一定能拿下！！下面我将已典型的题目为例子介绍几种常见的搜索方式。 1.二分搜索二分搜索代码模板：例题：#includeusingnamespacestd;doublen;constdoubleeps=1e-12;//二分搜索intmain(){ intt; cin>>t; while(t--){ cin>>n; doublel=0,r=100000,res=-1; while(ln)r=mid-0.0001; elseif(mid*mid*mid二分搜索是只能对有
十四届蓝桥青少组模拟赛Python-20221108 - 2
十四届蓝桥青少组模拟赛Python-20221108T1.二进制位数十进制整数2在十进制中是1位数，在二进制中对应10，是2位数。十进制整数22在十进制中是2位数，在二进制中对应10110，是5位数。请问十进制整数2022在二进制中是几位数？print(len(bin(2022))-2)#运行结果：11T2.晨跑小蓝每周六、周日都晨跑，每月的1、11、21、31日也晨跑。其它时间不晨跑。已知2022年1月1日是周六，请问小蓝整个2022年晨跑多少天？#样例代码1ls=[0,31,28,31,30,31,30,31,31,30,31,30,31]ans=0k=6foriinrange(1,13)
蓝桥杯 stm32 MCP4017 - 2
本文代码使用HAL库。文章目录前言一、MCP4017的重要特性二、MCP4017计算RBW阻值三、MCP4017地址四、MCP4017读写函数五、CubeMX创建工程（利用ADC测量MCP4017电压）、对应代码：总结前言一、MCP4017的重要特性蓝桥杯板子上的是MCP4017T-104ELT，如图1。MCP4017是一个可编程电阻，通过写入的数值可以改变电阻的大小。重点在于6引脚（W），5引脚（B&#
[蓝桥杯单片机]学习笔记——串口通信的基本原理与应用 - 2
目录一、原理部分1、什么是串行通信（1）并行通信与串行通信（2）串行通信的制式（3）串行通信的主要方式 2、配置串口（1）SCON和PCON：串行口1的控制寄存器（2）SBUF：串行口数据缓冲寄存器（3）AUXR：辅助寄存器编辑（4）ES、PS：与串行口1中断相关的寄存器（5）波特率设置 3、串口框架编写二、程序案例一、原理部分1、什么是串行通信（1）并行通信与串行通信微控制器与外部设备的数据通信，根据连线结构和传送方式的不同，可以分为两种：并行通信和串行通信。并行通信：数据的各位同时发送与接收，每个数据位使用一条导线，这种方式传输快，但是需要多条导线进行信号传输。串行通信：数据一位一
ruby - 针对每一行的多个(15+)正则表达式解析文本正文的最佳方法是什么？ - 2
我有一段文本需要扫描，每行至少包含2部分信息，有时包含4部分信息。问题是每一行可能是15-20种不同操作中的一种。在ruby中，当前代码看起来像这样:text.split("\n").eachdo|line|#around20times................expressions['actions'].eachdo|pat,reg|#around20times.................这显然是“问题所在”。通过将所有正则表达式合并为一个，我确实设法使其更快(在C++中提高了50%)，但这仍然不是我需要的速度——我需要快速解析数千个这些文件!现在我将它们与正则表达式