BFS的基本应用——flood fill 最短路

bfs的核心就是一层一层往外扩展，在bfs中会用到一个队列，又由于是一层一层往外扩展的，故而可以用来求连通的问题，同时相当于每次往外扩展的边权都是1，所以这个队列是有序的，相当于dijkstra算法中的优先队列，那么也可以用来求边权为1的最短路问题。

Flood Fill

Flood Fill问题实际就是连通块问题，可以求二维图中连通块的数量，连通块的面积，连通块与非连通块之间的关系，连通块的边界、周长等问题。核心就是在在搜到非连通位置时的不同处理。

另外连通分四连通和八连通，四连通可以用向量来解决，而八连通可以直接围绕当前访问的点访问一个3*3的矩形，然后将中间那一块儿扣掉，当然向量也可以。

另外用到的队列既可以用queue，也可以用数组来模拟。

1097. 池塘计数（活动 - AcWing）

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> pii;
pii q[1000010];
int hh,tt;
int st[1010][1010];
int n,m;
char s[1010][1010];
void bfs(int a,int b)
{
    st[a][b]=1;
    hh=tt=0;
    q[tt++]={a,b};
    while(hh<tt)
    {
        auto t=q[hh++];
        for(int i=t.x-1;i<=t.x+1;i++)
        {
            for(int j=t.y-1;j<=t.y+1;j++)
            {
                if(i==t.x&&j==t.y) continue;
                if(i<1||i>n||j<1||j>m) continue;
                if(s[i][j]!='W'||st[i][j]) continue;
                q[tt++]={i,j};
                st[i][j]=1;
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
    int c=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(!st[i][j]&&s[i][j]=='W')
            {
                c++;
                bfs(i,j);
            }
        }
    }
    cout<<c;
}

 1098. 城堡问题（活动 - AcWing）

 

思路：这题看上去比较麻烦，因为它不是相邻的格子有阻碍，而是用一个数来表示当前位置四周的情况，而且这里还需要求面积。我们先来看它给定的数1,2,4,8，显然就是二进制数的某一位，那么我们实际上可以直接bfs，用该点上的数来判断将要延伸的位置是否可以达到就好。另外面积也很简单，给bfs加个返回值就好。

 

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> pii;
pii q[2500];
int hh,tt;
int n,m;
int st[100][100];
int g[100][100];
int dx[]={0,-1,0,1};
int dy[]={-1,0,1,0};
int bfs(int a,int b)
{
    st[a][b]=1;
    hh=tt=0;
    q[tt++]={a,b};
    int s=0;
    while(hh<tt)
    {
        auto t=q[hh++];
        s++;
        for(int i=0;i<4;i++)//0
        {
            int nx=t.x+dx[i],ny=t.y+dy[i];
            if(nx<1||nx>n||ny<1||ny>m) continue;
            if(st[nx][ny]) continue;
            if(g[t.x][t.y]>>i&1) continue;//说明有墙
            q[tt++]={nx,ny};
            st[nx][ny]=1;
        }
    }
    return s;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&g[i][j]);
        }
    }
    int mx=0,c=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(!st[i][j])
            {
                c++;
                int tmp=bfs(i,j);
                mx=max(mx,tmp);
            }
        }
    }
    cout<<c<<endl<<mx;
}

1106. 山峰和山谷(活动 - AcWing)

思路：这里就涉及到对边界值的处理，我们只需要在访问到边界的时候判断一下非连通块位置的值，与连通块之间的关系即可。因为要记录一下情况，所以我们多传两个参数进函数即可，另外一定要注意，这里需要传地址，不能只传值，只有数组传值可以进行改变。

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> pii;
pii q[1000010];
int st[1010][1010];
int g[1010][1010];
int n,hh,tt;
void bfs(int a,int b,int&h,int&v)
{
    st[a][b]=1;
    hh=tt=0;
    q[tt++]={a,b};
    while(hh<tt)
    {
        auto t=q[hh++];
        for(int i=t.x-1;i<=t.x+1;i++)
        {
            for(int j=t.y-1;j<=t.y+1;j++)
            {
                if(i==t.x&&j==t.y) continue;
                if(i<1||i>n||j<1||j>n) continue;
                if(g[i][j]>g[t.x][t.y]) h++;
                else if(g[i][j]<g[t.x][t.y]) v++;
                else 
                {
                    if(st[i][j]) continue;//因为要看非连通位置，所以在加入队列之前再判断是否出现过
                    q[tt++]={i,j};
                    st[i][j]=1;
                }
            }
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) 
            scanf("%d",&g[i][j]);

    int sf=0,sg=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(!st[i][j])
            {
                int h=0,v=0;
                bfs(i,j,h,v);
                if(h&&v) continue;
                else if(v) sf++;//有比它矮的
                else if(h) sg++;//有比它高的
                else sf++,sg++;
            }
        }
    }
    cout<<sf<<" "<<sg;
}

最短路问题

这里的最短路问题有个条件就是每一步的权重都相等（未必都是1，只要相等即可），根据bfs中队列的性质，每个位置第一次被扫到的时候，那么进行的操作数或者走过的路径就是最短路。

1076. 迷宫问题（活动 - AcWing）

 

思路：这里输出最短路，我们的处理就是记录每个位置是由谁转移而来的。相当于将st数组变成pair<int,int>的类型，我们因为这里的左边是从0开始的，那么我们可以将st初始化成-1，memset(st,-1,sizeof st),那么每个st的第一位和第二位就是-1，我们查找的时候只用判断一下就知道这个位置是否已经被搜过了。另外免得再存一遍，我们可以从终点往起点搜。

而且这里的搜索也不再是遍历了，而是从某一个点开始搜。

#include<bits/stdc++.h>
using namespace std;
#define x first 
#define y second
typedef pair<int,int> pii;
pii q[1000010];
pii st[1010][1010];
int hh,tt;
int n;
int g[1010][1010];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
void bfs(int a,int b)
{
    memset(st,-1,sizeof st);
    st[a][b]={a,b};
    hh=tt=0;
    q[tt++]={a,b};
    while(hh<tt)
    {
        auto t=q[hh++];
        for(int i=0;i<4;i++)
        {
            int nx=t.x+dx[i],ny=t.y+dy[i];
            if(nx<0||nx>=n||ny<0||ny>=n) continue;
            if(st[nx][ny].x!=-1) continue;
            if(g[nx][ny]==1) continue;
            st[nx][ny]={t.x,t.y};
            q[tt++]={nx,ny};
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++) 
            scanf("%d",&g[i][j]);
    bfs(n-1,n-1);
    pii e(0,0);//表示定义一个名为e的pair<int,int>类型的变量，初值赋为{0，0}
    while(1)
    {
        cout<<e.x<<" "<<e.y<<endl;
        if(e.x==n-1&&e.y==n-1) break;
        e=st[e.x][e.y];
    }
}

188. 武士风度的牛(188. 武士风度的牛 - AcWing题库)

 

思路：就相当于马走日，从一个点到另一个点最少多少步，那么就是一个bfs宽搜问题。 不过这里需要注意的是，中间有障碍物可能有些位置需要判断一下。

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> pii;
pii q[40010];
int n,m,hh,tt;
char s[200][200];
int ex,ey;
int d[200][200];
int st[200][200];
int dx[]={1,1,-1,-1,2,2,-2,-2};
int dy[]={2,-2,2,-2,1,-1,1,-1};
void bfs(int sx,int sy)
{
    memset(d,0x3f,sizeof d);
    d[sx][sy]=0;
    st[sx][sy]=1;
    hh=tt=0;
    q[tt++]={sx,sy};
    while(hh<tt)
    {
        auto t=q[hh++];
        for(int i=0;i<8;i++)
        {
            int nx=t.x+dx[i],ny=t.y+dy[i];
            if(nx<1||nx>n||ny<1||ny>m) continue;
            if(st[nx][ny]) continue;
            if(s[nx][ny]=='*') continue;
            q[tt++]={nx,ny};
            d[nx][ny]=d[t.x][t.y]+1;
            st[nx][ny]=1;
        }
    }
}
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
    int sx,sy;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(s[i][j]=='K') sx=i,sy=j;
            if(s[i][j]=='H') ex=i,ey=j;
        }
    }
    bfs(sx,sy);
    //printf("%d %d %d %d\n",sx,sy,ex,ey);
    cout<<d[ex][ey];
}

 ps：这题的陷阱在于先输入列数再输入行数，记得交换一下。

1100. 抓住那头牛（活动 - AcWing）

这里虽然是在数轴上，但仍旧是每个点有三种操作，求到另一个点的最短路，看着有点像贪心，但是实际上就是bfs暴搜。另外要注意一点，当牛在左边时，+1和2倍的操作都没有意义了，所以右边界实际上是2e5。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5;
int n,m;
int d[N],st[N],q[N],hh,tt;
void bfs(int s)
{
    st[s]=1;
    d[s]=0;
    hh=tt=0;
    q[tt++]=s;
    while(hh<tt)
    {
        auto t=q[hh++];
        if(0<=t+1&&t+1<=N&&!st[t+1]) 
        {
            d[t+1]=d[t]+1;
            st[t+1]=1;
            q[tt++]=t+1;
        }
        if(0<=t-1&&t-1<=N&&!st[t-1]) 
        {
            d[t-1]=d[t]+1;
            st[t-1]=1;
            q[tt++]=t-1;
        }
        if(0<=2*t&&2*t<=N&&!st[2*t]) 
        {
            d[2*t]=d[t]+1;
            st[2*t]=1;
            q[tt++]=2*t;
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    bfs(n);
    cout<<d[m];
}

 ps:一定要注意左边界可以到0.

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

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

相关文章

vue3学习——初始化项目及配置

vue3学习——初始化项目及配置

初始化项目 环境 node 16pnpm 8.0.0 命令 pnpm create vite进行以下选择 &#x1f447; – 项目名 – VUe – Ts – cd/目录 – pnpm run dev 浏览器自动打开 package.json 配置eslint 安装依赖包 pnpm i eslint -D npx eslint --init // 生成配置文件进行以下选择 &a…
阅读更多...
SpringBoot 使用WebSocket功能

SpringBoot 使用WebSocket功能

实现步骤&#xff1a; 1.导入WebSocket坐标。 在pom.xml中增加依赖项&#xff1a; <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-websocket</artifactId> </dependency>2.编写WebSocket配…
阅读更多...
Redis学习——高级篇⑨

Redis学习——高级篇⑨

Redis学习——高级篇⑨ Redis7高级之Redlock算法和Redisson的使用&#xff08;十&#xff09; 10.1 Redlock 红锁算法1.解决手写分布式锁的单点故障问题2.设计理念3. 解决方案 10.2 Redisson进行代码改造10.3 多机案例&#xff08;解决单点故障&#xff09;10.4 R…
阅读更多...
vue3使用is动态切换组件报错Vue received a Component which was made a reactive object.

vue3使用is动态切换组件报错Vue received a Component which was made a reactive object.

vue3使用is动态切换组件&#xff0c;activeComponent用ref定义报错 Vue received a Component which was made a reactive object. This can lead to unnecessary performance overhead, and should be avoided by marking the component with markRaw or using shallowRef ins…
阅读更多...
代码随想录算法训练营29期|day36任务以及具体安排

代码随想录算法训练营29期|day36任务以及具体安排

第八章 贪心算法 part05 435. 无重叠区间 class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, (a,b)-> {return Integer.compare(a[0],b[0]);});if(intervals.length 1) return 0;int result 0;for(int i 1 ; i < interva…
阅读更多...
结构体与共用体——共用体——C语言——day16

结构体与共用体——共用体——C语言——day16

昨天介绍了下结构体&#xff0c;今天主要介绍共用体&#xff0c;枚举 共用体 概念&#xff1a;有时需要使几种不同类型的变量存放到同一段内存单元中。 例如&#xff0c;可把一个整型变量、一个字符型变量、一个浮点型变量放在同一个地址开始的内存单元中 。以上三个变量在内…
阅读更多...
Python系列-字典

Python系列-字典

&#x1f308;个人主页: 会编程的果子君 ​&#x1f4ab;个人格言:“成为自己未来的主人~” ​ 目录 ​ 字典是什么 创建字典 查找key 新增/修改元素 删除元素 遍历字典元素 取出所有的key和value 合成的key类型 ​编辑 小结 字典是什么 字典是一种存储键值对的结…
阅读更多...
云打印怎么收费？云打印需要付费吗？

云打印怎么收费？云打印需要付费吗？

随着云打印概念的火热发展&#xff0c;很多有打印需求的App或者个人用户都想使用易绘创云打印服务。那么易绘创云打印怎么收费&#xff1f;云打印需要付费吗&#xff1f;今天就带大家来了解一下。 云打印怎么收费&#xff1f;云打印需要付费吗&#xff1f; 很多有打印需求的小…
阅读更多...
Linux网络状态查看与防火墙管理

Linux网络状态查看与防火墙管理

网络状态查看 netstat [选项] Netstat是一款命令行工具&#xff0c;用于显示Linux系统中网络的状态信息&#xff0c;可以显示网络连接、路由表、连接的数据统计等信息。 使用 选项 -a&#xff1a;显示所有选项&#xff0c;包括监听和未监听的端口。 -t&#xff1a;仅显示tc…
阅读更多...
IS-IS的LSP分片扩展

IS-IS的LSP分片扩展

原理 IS-IS通过泛洪LSP来宣告链路状态信息，由于一个LSP能够承载的信息量有限，IS-IS将对LSP进行分片。每个LSP分片由产生该LSP的结点或伪结点的SystemID、PseudnodeID（普通LSP中该值为0，Pseudonode LSP中该值为非0）、LSPNumber（LSP分片号）组合起来唯一标识，由于LSPNumb…
阅读更多...
微信小程序（二十四）简易的双向绑定

微信小程序（二十四）简易的双向绑定

注释很详细&#xff0c;直接上代码 上一篇 新增内容&#xff1a; 1.双向绑定实例 2.双向绑定的局限性 源码&#xff1a; index.wxml <!-- 1.placeholder:输入框为空时的占位提示语2.model:value 双向绑定&#xff08;其实就是在原先基础上加上了model:&#xff09; 3.目前双…
阅读更多...
小白水平理解面试经典题目LeetCode 118 Pascal‘s Triangle【Java实现】

小白水平理解面试经典题目LeetCode 118 Pascal‘s Triangle【Java实现】

LeetCode 118 生成杨辉三角&#xff08;Pascal’s Triangle&#xff09; 小白渣翻译 给定一个非负整数 numRows&#xff0c;生成杨辉三角的前 numRows 行。 在杨辉三角中&#xff0c;每个数是它左上方和右上方的数的和。 例子 这里是小白理解 那么这种题目一上来看&#xf…
阅读更多...
C++进阶（九）哈希概念哈希函数哈希冲突

C++进阶（九）哈希概念哈希函数哈希冲突

&#x1f4d8;北尘_&#xff1a;个人主页 &#x1f30e;个人专栏:《Linux操作系统》《经典算法试题 》《C》 《数据结构与算法》 ☀️走在路上&#xff0c;不忘来时的初心 文章目录 一、哈希概念1、哈希介绍2、哈希与哈希表 二、哈希冲突三、哈希函数四、 哈希冲突解决 一、哈…
阅读更多...
ElementUI Form：Checkbox 多选框

ElementUI Form：Checkbox 多选框

ElementUI安装与使用指南 Checkbox 多选框 点击下载learnelementuispringboot项目源码 效果图 el-checkbox.vue &#xff08;Checkbox 多选框&#xff09;页面效果图 项目里el-checkbox.vue代码 <script> const cityOptions [上海, 北京, 广州, 深圳] export def…
阅读更多...
react 之 UseMemo

react 之 UseMemo

useMemo 看个场景 下面我们的本来的用意是想基于count的变化计算斐波那契数列之和&#xff0c;但是当我们修改num状态的时候&#xff0c;斐波那契求和函数也会被执行&#xff0c;显然是一种浪费 // useMemo // 作用&#xff1a;在组件渲染时缓存计算的结果import { useState …
阅读更多...
【C++干货铺】哈希结构在C++中的应用

【C++干货铺】哈希结构在C++中的应用

目录 unordered系列关联式容器 unordered_map unordered_map的接口说明 1.unordered_map的构造 2. unordered_map的容量 3. unordered_map的迭代器 4. unordered_map的元素访问 5. unordered_map的查询 6. unordered_map的修改操作 7. unordered_map的桶操作 底层结构 …
阅读更多...
Nijijourney V6版本动漫图像生成模型发布

Nijijourney V6版本动漫图像生成模型发布

简介 这是一个最先进的AI&#xff0c;可以绘制任何二次元风格的绘画&#xff01;这是一个由 Spellbrush 与 Midjourney 所共同设计开发的魔法般工具。无论您是在寻找可爱的Q版角色还是充满动感的动作场景&#xff0c;niji・journey 都能将您的想象变为现实。 功能介绍 - 增强…
阅读更多...
深度解析：i++ 与 ++i，探究其性能差异与使用技巧

深度解析：i++ 与 ++i，探究其性能差异与使用技巧

在编程世界中&#xff0c;经常会遇到对变量进行递增操作&#xff0c;而i和i这两个递增操作符就是我们常用的两种方式。这两者看似简单&#xff0c;但却有着微妙的性能区别和使用差异。 1. 性能差异的探究 首先&#xff0c;我们来研究i和i在性能上的微妙差异。这对于编写高效的…
阅读更多...
搭建 idea 插件仓库私服

搭建 idea 插件仓库私服

正常情况下&#xff0c;我们开发的 idea 插件会发布到 idea 官方商城中&#xff0c;这样用户就可以在 idea 的 Marketplace 中搜索安装。 但是在企业内部&#xff0c;有可能我们开发了很多内部插件&#xff0c;而不能发布到公共市场中&#xff0c;这种情况下我们就需要搭建一个…
阅读更多...
子查询练习1

子查询练习1

数据表 链接&#xff1a;https://pan.baidu.com/s/1dPitBSxLznogqsbfwmih2Q 提取码&#xff1a;b0rp --来自百度网盘超级会员V5的分享 子查询举例 子查询的分类 单行子查询 > > < < ! <> 单行子查询 WHERE中的子查询 查询工资大于149号…
阅读更多...
最新文章

Copyright @ 2022~2023