[第五章]图论&&BFS

这篇具有很好参考价值的文章主要介绍了[第五章]图论&&BFS。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

本专栏内容为:算法学习专栏,分为优选算法专栏,贪心算法专栏,动态规划专栏以及递归,搜索与回溯算法专栏四部分。 通过本专栏的深入学习,你可以了解并掌握算法。

💓博主csdn个人主页:小小unicorn
⏩专栏分类:算法从入门到精通
🚚代码仓库:小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识

献给阿尔吉侬的花束:

[第五章]图论&&BFS,算法专栏,蓝桥杯训练营,图论,宽度优先,算法

算法原理:

用 a[N][N] 接收地图。
dis[N][N] 存储到每个点的路径长度。

从起点出发,广度优先遍历地图:

起点入队。
如果队列非空,一直执行下面语句:

  1. 队头出队。
  2. 遍历队头的上下左右四个方向:如果是 ‘.’ 走过去,并且该位置入队,该点对应的dis值更新为队头的dis + 1,该点更新为’#',表示走过了。如果是 ‘#’ 不做处理,如果是 ‘E’,走到了终点,输出该点对应的 dis 值。

如果队列为空,还没有找到终点,则无法到达,输出 oop!。

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int, int> PII;

const int N = 210;

char a[N][N];
int dis[N][N];

void bfs(PII start)
{
    queue<PII> q;
    q.push(start);//队头队,对应步骤1
    while(!q.empty())
    {
        PII u = q.front();
        q.pop();
        int dx[4] = {-1, 0, 1, 0};
        int dy[4] = {0, 1, 0 ,-1};
        for(int i = 0; i < 4; i++)//遍历四个方向,对应步骤2
        {
            int x = u.first + dx[i];
            int y = u.second + dy[i];
            
            if(a[x][y] == '#') continue;//如果是'#',不做任何处理
            if(a[x][y] == '.')//如果是 '.',更新对应内容
            {
                dis[x][y] = dis[u.first][u.second] + 1;
                a[x][y] = '#';
                q.push({x, y});
            }
            if(a[x][y] == 'E')//如果是'E',找到了,输出
            {
                cout << dis[u.first][u.second] + 1 << endl;
                return;
            }
        }
    }
    cout << "oop!" << endl;//没有找到

}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        memset(a, '#', sizeof(a));//初始化地图,各个点都是墙。
        memset(dis, 0, sizeof(dis));//初始化dis
        int n,m;
        PII start;
        cin >> n >> m;
        for(int i = 1; i <= n; i++)//从第一行存储地图,因为四周都是墙,bfs时,可以不做越界判断
        {
            for(int j = 1; j <= m; j++)//从第一;列存储地图,因为四周都是墙,bfs时,可以不做越界判断
            {
                cin >> a[i][j];
                if(a[i][j] == 'S')//记录下起点位置。
                    start.first = i, start.second = j, a[i][j] = '#';
            }
        }
        bfs(start);
    }
}

说明一下,地图初始化为全是墙,然后把地图存储在a[1][1] ~ a[n][m]后,地图四周会被墙包围,所以 bfs 的时候,不用做地图越界处理了。

红与黑

[第五章]图论&&BFS,算法专栏,蓝桥杯训练营,图论,宽度优先,算法

算法原理:

深度优先遍历算法。

对于某个点执行如下算法:

  1. 从该点出发,如果可以往上走就往上走,对上方点递归执行该算法。

  2. 从该点出发,如果可以往右走就往右走,对右方点递归执行该算法。

  3. 从该点出发,如果可以往下走就往下走,对下方点递归执行该算法。

  4. 从该点出发,如果可以往左走就往左走,对左方点递归执行该算法。

#include <cstring>
#include <iostream>
using namespace std;

const int N = 25;

int n, m;
char g[N][N];//存储地板


int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//上右下左四个方向

int dfs(int x, int y)//深度优先遍历
{
    int cnt = 1;

    g[x][y] = '#';
    for (int i = 0; i < 4; i ++ )//走四个方向
    {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= n || b < 0 || b >= m) continue;
        if (g[a][b] != '.') continue;
        cnt += dfs(a, b);//如果可以走向某一个方向,对该方向上的点递归
    }

    return cnt;
}

int main()
{
    while (cin >> m >> n, n || m)
    {
        for (int i = 0; i < n; i ++ ) cin >> g[i];//一次读入一行

        int x, y;
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                if (g[i][j] == '@')
                {
                    x = i;
                    y = j;
                }

        cout << dfs(x, y) << endl;
    }

    return 0;
}

交换瓶子

[第五章]图论&&BFS,算法专栏,蓝桥杯训练营,图论,宽度优先,算法

算法原理:

暴力枚举

1、通过观察可以发现,我们每一个数都必须回到它自己的位置上,比如 1 必须在第一位,2 必须在第二位上

2、那么我们就可以这样操作,由于每个数必须回到自己的位置,直接从 1 枚举到 n n n ,如果当前位置的数不等于它的下标,那么我们就必须要把它给替换掉

3、设当前位置为 i i i 的话,那么我们就从 i + 1 i+1 i+1 开始往后枚举,直到找到对应的 a[ j j j] 和我们的 i i i 相等,那么我们就把上个数交换,把交换次数++

4、容易证明这个算法的正确性,由于每个数必须回到原来的位置,所以我们这样子操作不会出现多于的步骤,因为每次操作都是必须的,即使这个算法看起来很麻烦

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>

using namespace std;

const int N=10010;

int n;

int a[N];

int main()
{
    scanf("%d",&n);
    
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]!=i)//直接遍历,如果不是自身的话,我们必然要交换,所以不会出现多于的操作
        {
            for(int j=i+1;j<=n;j++)
            if(a[j]==i)
             swap(a[i],a[j]);
             
             sum++;
        }
    }
    
    printf("%d\n",sum);
    
    return 0;
}

完全二叉树的权值

[第五章]图论&&BFS,算法专栏,蓝桥杯训练营,图论,宽度优先,算法

算法原理:

前置:完全二叉树性质

对于第 i i i 层,保证存在 2 i − 1 2^{i-1} 2i1 个结点的满二叉树。

题目思路:

对于每一层的和,我们可以用 h h h 数组进行存储:

h 1 h_1 h1 = ∑ i = 2 1 − 1 2 1 − 1 ( a i ) \sum\limits^{2^{1}-1}_{i=2^{1-1}}(a_i) i=211211(ai)

h 2 h_2 h2 = ∑ i = 2 2 − 1 2 2 − 1 ( a i ) \sum\limits^{2^{2}-1}_{i=2^{2-1}}(a_i) i=221221(ai)

h 3 h_3 h3 = ∑ i = 2 3 − 1 2 3 − 1 ( a i ) \sum\limits^{2^{3}-1}_{i=2^{3-1}}(a_i) i=231231(ai)

h 4 h_4 h4 = ∑ i = 2 4 − 1 2 4 − 1 ( a i ) \sum\limits^{2^{4}-1}_{i=2^{4-1}}(a_i) i=241241(ai)

是不是发现突然很简单?对于每个 h i h_i hi,我们可以求 ∑ j = 2 i − 1 2 i − 1 ( a j ) \sum\limits^{2^{i}-1}_{j=2^{i-1}}(a_j) j=2i12i1(aj) 就行啦!

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int INF = 0x7ffffff;

int n;

int a[1 << 17], h[17];//2^17 > 10^5

signed main() {
    
    scanf ("%lld", &n);
    
    for (int i = 1; i <= n; i ++) 
    	scanf ("%lld", a + i);
    	//读入 ai,因为 n 的大小是 10^5, 所以用 scanf 这类较快的读入方式。
    	
    int i = 1, j = 0;
    
    while (i <= n) {
    	
    	++ j;
    	
    	while (i < pow (2, j)) {//从 2^(j-1) 循环到 2^j-1
    		
    		h[j] += a[i ++];
		}
	}
	
	int maxx = -INF, res = 0;//找最大
	
	for (i = 1; i <= j; i ++)
		if (h[i] > maxx) 
		
			maxx = h[i],
			res = i;
			
	printf ("%lld\n", res);

    return 0;
}

地牢大师

[第五章]图论&&BFS,算法专栏,蓝桥杯训练营,图论,宽度优先,算法

算法原理:

分析

  • 该迷宫为立体,故需要三维数组构建迷宫模型

  • 要求第一次搜到的点即为答案,则考虑BFS

  • 记录SE的位置,S为搜索开始的点,E为搜索结束点

  • 搜索过程中的每个位置需要向六个方向偏移,需要[偏移量]数组

  • 偏移点需满足的要求:不越界,未走过,不能是墙#

#include <bits/stdc++.h>
using namespace std;

const int N=110;

int l,r,c;  //迷宫参数
int px,py,pz,ex,ey,ez;  //pi为S的位置,ei为E的位置

char mp[N][N][N];  //记录迷宫
int ans[N][N][N];  //存储答案
bool vis[N][N][N];  //记录该点是否走过的状态

struct point{  //点的坐标
    int x,y,z;
};

queue<point> st;  //搜索队列

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

int bfs(){
    while(!st.empty()){  //当队头不为空时,扩展搜索队头
        auto p=st.front();
        for(int i=0;i<6;i++){
            int m_x=p.x+dx[i],m_y=p.y+dy[i],m_z=p.z+dz[i];  //偏移之后的点的坐标
            if(m_x<=l&&m_y<=r&&m_z<=c&&m_x>=1&&m_y>=1&&m_z>=1&&!vis[m_x][m_y][m_z]&&mp[m_x][m_y][m_z]!='#'){  //判断条件
                vis[m_x][m_y][m_z]=1;  //更新该点走过的状态
                ans[m_x][m_y][m_z]=ans[p.x][p.y][p.z]+1;  //更新偏移后的点距离S的步骤
                if(mp[m_x][m_y][m_z]=='E') return  ans[m_x][m_y][m_z];  //搜到E直接返回答案
                st.push({m_x,m_y,m_z});  //将该点入队,继续扩展搜索
            }
        }
        st.pop();  //队头扩展搜索完毕后出队
    }
    return 0;  //所有的点扩展搜索完后若还未返回搜到E,说明无解
}

int main(){
    while(cin>>l>>r>>c&&l&&r&&c){  //多实例读入
        //还原数据
        memset(ans,0,sizeof(ans)); 
        memset(mp,0,sizeof(mp));
        memset(vis,0,sizeof(vis));
        while(st.size()){
            st.pop();
        }
        //读入迷宫
        for(int i=1;i<=l;i++){
            for(int j=1;j<=r;j++){
                for(int k=1;k<=c;k++){
                    cin>>mp[i][j][k];
                    if(mp[i][j][k]=='S') px=i,py=j,pz=k;  //
                    if(mp[i][j][k]=='E') ex=i,ey=j,ez=k;  //
                }
            }
        }
        
        vis[px][py][pz]=1;  //标记S已经走过
        
        st.push({px,py,pz}); //S点入队
        
        int cnt=bfs();  //调用搜索,将从S点开始搜索
        
        if(cnt!=0) printf("Escaped in %d minute(s).\n",cnt);
        else cout<<"Trapped!"<<endl;
    }
    return 0;
}

全球变暖

[第五章]图论&&BFS,算法专栏,蓝桥杯训练营,图论,宽度优先,算法

算法原理

题目一看就是“连通块问题”,是基础搜索。用DFS或BFS都行:遍历一个连通块(找到这个连通块中所有的’#‘,并标记已经搜过,不用再搜);再遍历下一个连通块…;遍历完所有连通块,统计有多少个连通块。

回到题目,什么岛屿不会被完全淹没?若岛中有个陆地(称为高地),它周围都是陆地,那么这个岛不会被完全淹没。
  用DFS或BFS搜出有多少个岛(连通块),并且在搜索时统计那些没有高地的岛(连通块)的数量,就是答案。
  因为每个像素点只用搜一次且必须搜一次,所以复杂度是 O ( n 2 ) O(n^2) O(n2)的,不可能更好了。文章来源地址https://www.toymoban.com/news/detail-852287.html

#include<bits/stdc++.h>
using namespace std;

int n;
char a[1010][1010]; //地图
int vis[1010][1010]={0};  //标记是否搜过
int d[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}}; //四个方向
int flag;  //用于标记这个岛中是否被完全淹没
void dfs(int x, int y)
{
    vis[x][y] = 1;      //标记这个'#'被搜过。注意为什么可以放在这里
    if(a[x][y+1]=='#' && a[x][y-1]=='#' && a[x+1][y]=='#' && a[x-1][y]=='#')
        flag = 1;       //上下左右都是陆地,不会淹没
    for(int i = 0; i < 4; i++){ //继续DFS周围的陆地
        int nx = x + d[i][0], ny = y + d[i][1];
      //if(nx>=1 && nx<=n && ny>=1 && ny<=n && vis[nx][ny]==0 && a[nx][ny]=='#') //题目说边上都是水,所以不用这么写了
        if(vis[nx][ny]==0 && a[nx][ny]=='#') //继续DFS未搜过的陆地,目的是标记它们
            dfs(nx,ny);
    }
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin >> a[i][j];
    int ans = 0 ;
    for(int i = 1; i <= n; i++)  //DFS所有像素点
        for(int j = 1; j <= n; j++)
            if(a[i][j]=='#' && vis[i][j]==0)
            {
                flag = 0;
                dfs(i,j);
                if(flag == 0)  //这个岛全部被淹
                    ans++;     //统计岛的数量
            }
    cout<<ans<<endl;
    return 0;
}

到了这里,关于[第五章]图论&&BFS的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【优选算法专栏】专题十六:BFS解决最短路问题---前言

    本专栏内容为:算法学习专栏,分为优选算法专栏,贪心算法专栏,动态规划专栏以及递归,搜索与回溯算法专栏四部分。 通过本专栏的深入学习,你可以了解并掌握算法。 💓博主csdn个人主页:小小unicorn ⏩专栏分类:算法从入门到精通 🚚代码仓库:小小unicorn的代码仓库

    2024年04月15日
    浏览(49)
  • 【算法】动态规划(第五章习题解答)

    5.1 图书馆大门前有 n n n 级台阶, 你每次跨上 1 1 1 级或者 2 2 2 级, 请问等上 n n n 级台阶总共有多少种不同的方法? 设计一个算法求解上述问题, 尝试写出公式, 说明算法设计思想和时间复杂度. 算法设计:核心思路是函数的递归调用,当处理 n n n 级台阶时,如果跨上1级则还需要

    2024年02月02日
    浏览(43)
  • 第五章 数据结构与算法——八大排序

    目录 一、排序的概念及其运用 二、八大排序的原理及其实现(升序为例) (一)、直接插入排序 (二)、希尔排序(也叫缩小增量排序)(重要) 1.原理: 2.该排序一般分为两个步骤: 3.预排序过程: 4.预排序的意义(升序为例): 5.希尔排序的特点: 6.希尔排序代码实现

    2024年02月19日
    浏览(49)
  • 红与黑(bfs + dfs 解法)(算法图论基础入门)

    献给阿尔吉侬的花束( 入门级bfs查找 + 模版解读 + 错误示范 在之前的博客当中,详细地介绍了这类题目的解法,今天为大家带来一道类似的题目练练手,后续还会更新更有挑战的题目以及更为详细的解析,喜欢的小伙伴可以点个关注啦! 有一间长方形的房子,地上铺了红色、

    2024年01月20日
    浏览(52)
  • 算法-双指针、BFS与图论-1101. 献给阿尔吉侬的花束

    题目 思路 BFS可以搜环,有环也没有关系,如果有解:一定可以找到一条最小步数的合法的路径 Python中 collections模块的详细用法介绍_python collections-CSDN博客 引用自上述文章: append(x):添加 x 到右端。 appendleft(x):添加 x 到左端。 clear():移除所有元素,使其长度为0. copy():创

    2024年03月14日
    浏览(50)
  • 【算法基础:搜索与图论】3.2 树与图的dfs和bfs

    要学会建树、建图的通用方法。 dfs 和 bfs 的代码框架。 https://www.acwing.com/problem/content/848/ 在 dfs 的过程中,统计各个节点作为断点时的连通块最大值。 https://www.acwing.com/problem/content/849/ 看到最短距离就可以想到使用宽搜。 注意! :题目中说明了 a 和 b 表示存在一条从 a 走到

    2024年02月16日
    浏览(37)
  • 第10天-代码随想录刷题训练-第五章 栈和队列- ● 理论基础 ● 232.用栈实现队列 ● 225. 用队列实现栈

    栈和队列对应的三个不同的STL版本,底层实现方式不一样, 为我们所知道的是 SGI STL 栈 栈提供 pop和push等接口, 不提供走访功能 也不提供迭代器, 不像map和set可以使用迭代器遍历,往往不被归类为容器,而是容器适配器 栈的内部实现结构可以使用 verctor、list 和 deque(默认)

    2024年02月04日
    浏览(39)
  • 【AcWing算法基础课】第五章 动态规划(未完待续)

    本专栏文章为本人AcWing算法基础课的学习笔记,课程地址在这。如有侵权,立即删除。 dp问题的优化 :在基本形式dp上作等价变形。 dp问题的解题方法 : 1)状态表示 集合 属性:最大值/最小值/数量。 2)状态计算 集合划分(不重不漏) 题目链接: 2. 01背包问题 - AcWing题库

    2024年02月12日
    浏览(62)
  • 数据结构与算法分析 第五章 树和二叉树 作业讲解

     参考教材: 《数据结构(C语言版 第2版)》 严蔚敏,李冬梅,吴伟民编著,人民邮电出版社,2022年版。 截图未标明出处均为原创或取自《数据结构(C语言版 第2版)》~   本文对应的作业题讲解视频:   数据结构与算法分析作业讲解视频合集 https://www.bilibili.com/video/BV1N

    2024年02月02日
    浏览(37)
  • C#,图论与图算法,图(Graph)广度优先遍历(BFS,Breadth First Search)算法与源代码

    深度优先算法(DFS,Deep First Search)与 宽度优先遍历(BFS,Breadth First Search) 是树、图数据结构的基础性、标准性的遍历算法。 深度优先搜索(DFS)是一种用于搜索图形或树数据结构的算法。该算法从树的根(顶部)节点开始,尽可能沿着给定的分支(路径)向下,然后回溯

    2024年03月23日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包