黄埔课堂-第一期BFS

china_history · 2025-06-09 22:08:52 · 算法·理论

有同学说自己不会BFS，自己手搓一个呗，这有何难，黄埔课堂现在开课。

bfs

有同学说，BFS是啥，我只能告诉你，非常的简而易之，也就是你从一个点开始，向他的四周（上下左右去寻找 )，如果这都听不懂的边做俯卧撑边听,怕你们做俯卧撑，我还画了个图：

是不是更加的简而易之了 我们的代码部分如下

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;//这个是不是看起来复而杂之，其实简而易之，pair可以帮我们储存一对的东西,比如坐标
char a[1001][1001];
int vis[1001][1001];//判断走没走过
int dx[4] = {0, -1, 0, 1};//方向数组，减代表上移一行，加代表下移一行
int dy[4] = {-1, 0, 1, 0};//减代表左移一列，加代表右移一列
int n, m;
int cnt = 0;
int s[100001];

void bfs(int x, int y) {//第一眼看到这个代码是不是蒙而逼之，其实简而易之。
    queue <pii> q;//建立一个代表坐标的队列，队列是一种先进先出的数据结构，我们的BFS是靠他实现的。
    vis[x][y] = cnt;//将当前点初始化
    q.push({x, y});
    while (!q.empty()) {//当队列里面有东西
        pii k = q.front();//取出
        q.pop();//弹出
        for (int i = 0; i < 4; i++) {
            int nx = k.first + dx[i];
            int ny = k.second + dy[i];
            if (nx < 1 || ny < 1 || nx > n || ny > n || abs(a[nx][ny] - '0' + a[k.first][k.second] - '0') != 1) {//判断条件
                continue;
            } else {
                if (vis[nx][ny] == 0) {//标一下，能走到的点送入队列
                    vis[nx][ny] = 1;
                    q.push({nx, ny});
                }
            }
        }
    }
}

课堂练习 p1141 ,p1135

下课

简单来说，BFS有手就会，优势在我，下课。