首页 > 其他分享 >初学bfs

初学bfs

时间:2022-10-23 23:14:04浏览次数:77  
标签:PII dist int bfs start 初学 end

dfs利用的是栈,bfs利用的是队列

如同y总所说的,不需要理解如何用队列实现一个bfs
而是跟着y总,告诉我们怎么做,然后我们自己判断一下这种是不是bfs
如图:取出的顺序和加入的顺序实际上都是bfs的顺序

一般的bfs框架形式如图:

由于bfs的层次遍历原理,它会优先遍历距离最短的点,因此相比dfs,它可以做到找最小步数的功能,或者说,最短路径
如图,右边的绿色数字即距离起点的距离大小(树的层数),由于从最短距离开始遍历,一直递增距离大小,可以找到最短的路径到达终点
并且由于判重数组的存在,bfs可以搜索含环的图

写一道模板题:https://www.acwing.com/problem/content/description/1103/

bfs写法:

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

#define x first
#define y second

using namespace std;

const int N = 210;

typedef pair<int, int> PII;

int n, m;
char g[N][N];
int dist[N][N];  // 把判重和距离数组合为一个

int bfs(PII start, PII end)  // 注意 start end都是PII类型的 别写错了
{
    queue<PII> q;

    memset(dist, -1, sizeof dist);  // 把距离数组都初始化成-1,-1表示无法达到

    dist[start.x][start.y] = 0;  // 起点开始,距离为0

    q.push(start);  // 将起点入队

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//上下左右的偏移量

    while(q.size())
    {
        PII t = q.front();
        q.pop();
        for (int i = 0; i < 4; i ++ )
        {
            int a = t.x + dx[i], b = t.y + dy[i]; 

            if (a < 0 || a >= n || b < 0 || b >= m) continue;  // 出界
            if (dist[a][b] != -1) continue;    // 重复
            if (g[a][b] == '#') continue;    // 障碍物
            dist[a][b] = dist[t.x][t.y] + 1;//满足条件能走,距离+1;
            if (end == make_pair(a, b)) return dist[a][b];  // 到终点了
            q.push({a, b});
        }
    }
    return -1;//无法达到
}
int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);
        PII start, end;
        for (int i = 0; i < n; i ++ )//寻找起点和终点
            for (int j = 0; j < m; j ++ )
                if (g[i][j] == 'S') start = {i, j};
                else if (g[i][j] == 'E') end = {i, j};
        int distance = bfs(start, end);
        if (distance == -1) printf("oop!\n");
        else printf("%d\n", distance);
    }
    return 0;
}

标签:PII,dist,int,bfs,start,初学,end
From: https://www.cnblogs.com/lxl-233/p/16818418.html

相关文章

  • 初学编程三大件之代码管理-->git的使用
    如果想成为一名合格的测试开发/自动化工程师,git知识是必不可少的。为什么这么说呢,因为如果想对代码进行版本管理,git工具是首选。下面说下什么是git :1.Git是一个开源的分......
  • bfs + bitmask
    864. ShortestPathtoGetAllKeysYouaregivenan mxn grid grid where:'.' isanemptycell.'#' isawall.'@' isthestartingpoint.Lowercas......
  • 初学c语言的感悟
          我现在已经大二了,大一下学期没有跟着老师学习,所以趁现在及时补救,在网上自学C语言。    我觉得学习C语言和学习英语差不多,有许多的规则,基本的语句......
  • 八数码难题——BFS
    原题链接:https://www.acwing.com/problem/content/847/通常情况下很难看出这是一道BFS题或者说看不出怎么表示状态,毕竟它的状态涉及到整个矩阵但是可以用一种unordered_......
  • Snowy Mountain (找规律来贪心+ 多源特殊bfs+根号n)
    题目大意:给定一棵 nn 个点的树,其中每个点可能是黑色或白色。一个点的高度定义为其距离最近黑色节点的距离。你初始在 ii 号节点上,势能为 00,可以做以下两种操作:......
  • 自学Java初学者的建议书
    基础  首选肯定的要明白java主要应用方向在哪,Java主要是用于web开发的。无论学习什么我们都知道,打好基础重要的重要性。但是Java的基础要想打扎实,并不是短时间内能做到的......
  • UESTC 482 Charitable Exchange(优先队列+bfs)
    CharitableExchangeTimeLimit:4000/2000MS(Java/Others)   MemoryLimit:65535/65535KB(Java/Others)Submit StatusHaveyoueverheardastarcharityshow......
  • HDU 1885 Key Task(BFS)
    KeyTaskTimeLimit:3000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):1809    AcceptedSubmission(s):770Pr......
  • ros2(galactic)初学者教程(下)
    使用colcon构建包背景colcon是ROS构建工具catkin_make、catkin_make_isolated、catkin_tools和ament_tools的迭代。有关colcon设计的更多信息,请参阅本文档。源代码可以......
  • Java学习——Spring初学
    最近几天有在开始学习Spring框架开发,虽说学的比较晚,但是自我感觉学习的很快 笔记:1.Spring的出现,是为了高效的完成软件开发,依照软件设计模式的“高内聚低耦合”原则......