欢迎光临
我们一直在努力
        找回密码
当前位置：171主机测评 > 服务器技术 > 正文

2025级大一ACM训练：搜索入门（一）：BFS

2026-01-31 分类：服务器技术 阅读(40) 评论(0)

介绍

本篇文章主要介绍三种bfs题型

  • 节点计数类（连通区域）：统计连通合法节点的总个数——瓷砖统计
  • 两点连通性判断类：判断起点能否到达终点——迷宫出入口
  • 最短路径 / 时间类：求起点到目标的最短步数 / 时间——小明出逃迷宫

    • 林大OJ 275：搜索字符串

    关注flag初始化的位置，每次在外层循环搜索时都要初始化flag为false，如果把flag改为int型应该会更好些。

    稍微改进一点：flag的赋值和使用绑定在同一个if块内，每次进入if块，都会先给flag赋初始值0，无残留污染。

    我第一次的代码：

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

    int main()
    {
    char a[1005],b[1005];
    int cnt;
    bool flag;
    while(cin>>a>>b)
    {
    cnt = 0;
    for(int i = 0; i<=strlen(a)-strlen(b); i++)
    {
    flag = false;
    if(a[i]==b[0])
    {
    flag = true;
    for(int j = 1; j<strlen(b); j++)
    {
    if(a[i+j] != b[j])
    {
    flag = false;
    break;
    }
    }
    }
    if(flag)
    cnt++;
    }
    cout<<cnt<<endl;
    }
    return 0;
    }

    我的第二版代码：

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

    int main()
    {
    char a[1005],b[1005];
    int cnt,flag;
    while(cin>>a>>b)
    {
    cnt = 0;
    for(int i = 0; i<=strlen(a)-strlen(b); i++)
    {
    if(a[i]==b[0])
    {
    flag = 0;
    for(int j = 1; j<strlen(b); j++)
    if(a[i+j] != b[j])
    {flag = 1; break;}
    if(flag==0) cnt++;
    }
    }
    cout<<cnt<<endl;
    }
    return 0;
    }

    林大OJ 558：迷宫寻路-搜索

    原始写法：发现合法节点，直接入队（此时节点还是*，未标记）运行600多ms！

    这种方式的问题：同一个节点会被多次加入队列，队列中存在大量重复节点。

    if(合法 && a[new_x][new_y]=='*') {
    q.push({new_x, new_y}); // 入队时不标记，还是*
    }

    Point temp = q.front();
    q.pop();
    a[temp.x][temp.y] = '#';

    改进：发现合法节点，先标记为#，再入队，当后续其他节点遍历到这个点，发现是#，直接跳过，不会入队，大大节省内存开销

    // 发现合法节点，先标记为#，再入队
    if(合法 && a[new_x][new_y]=='*') {
    a[new_x][new_y] = '#';
    q.push({new_x, new_y}); // 入队后，其他节点无法再找到这个*
    }

    //后续其他节点遍历到这个(new_x, new_y)，发现是#，直接跳过，不会入队

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

    struct Point
    {
    int x,y;
    };
    char a[1005][1005];
    int n,m,begin_x,begin_y,end_x,end_y,new_x,new_y;
    int dirs[4][2]={{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    queue<Point> q;
    void seek_begin()
    {
    for(int i = 0; i < n; i++)
    for(int j = 0; j < m; j++)
    if(a[i][j]=='*' && (i==0||i==n-1||j==0||j==m-1)){begin_x = i; begin_y = j; return;}
    }
    void seek_end()
    {
    for(int i = n-1; i >= 0; i–)
    for(int j = m-1; j >= 0; j–)
    if(a[i][j]=='*' && (i==0||i==n-1||j==0||j==m-1)){end_x = i; end_y = j; return;}
    }
    void bfs();

    int main()
    {
    ios::sync_with_stdio(false);
    while(cin>>n>>m){
    for(int i = 0; i < n; i++)
    cin>>a[i];
    bfs();
    }
    return 0;
    }

    void bfs()
    {
    while(!q.empty())
    {
    q.pop();
    }
    seek_begin();
    seek_end();
    q.push({begin_x,begin_y});
    a[begin_x][begin_y]='#';
    while( !q.empty())
    {
    Point temp = q.front();
    q.pop();
    if(temp.x == end_x && temp.y == end_y)
    {
    cout<<"YES"<<endl;
    return ;
    }
    for(int i = 0; i < 4; i++)
    {
    new_x=temp.x+dirs[i][0];
    new_y=temp.y+dirs[i][1];
    if(new_x>=0 && new_x<n && new_y>=0 && new_y<m && a[new_x][new_y]=='*')
    {
    a[new_x][new_y]='#';
    q.push({new_x, new_y});
    }
    }
    }
    cout<<"NO"<<endl;
    }

    林大OJ 784：白与黑-搜索

    这道题感觉和迷宫那道题差不多，只不过需要遍历每一个节点。要看清楚题目H和W表示的含义

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

    int W, H, begin_x, begin_y, cnt, new_x, new_y;
    char a[25][25];
    int dirc[4][2]={{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    struct Point{
    int x,y;
    };
    queue<Point> q;

    void seek_start()
    {
    for(int i = 0; i < H; i++)
    for(int j = 0; j < W; j++)
    if(a[i][j] == '@')
    {
    begin_x = i;
    begin_y = j;
    a[i][j] = '.';
    return;
    }
    }

    void bfs();

    int main()
    {
    ios::sync_with_stdio(false);
    while(cin>>W>>H && (W && H)){
    for(int i=0; i < H; i++)
    cin>>a[i];
    bfs();
    }
    return 0;
    }

    void bfs()
    {
    while(!q.empty())
    {
    q.pop();
    }

    cnt = 0;
    seek_start();
    q.push({begin_x, begin_y});
    a[begin_x][begin_y]='#';
    cnt++;

    while( !q.empty())
    {
    Point tmp = q.front();
    q.pop();
    for(int i=0; i < 4;i++)
    {
    new_x = tmp.x + dirc[i][0];
    new_y = tmp.y + dirc[i][1];
    if(new_x>=0 && new_x<H && new_y>=0 &&
    new_y<W && a[new_x][new_y]=='.')
    {
    a[new_x][new_y] = '#';
    q.push({new_x, new_y});
    cnt++;
    }
    }
    }
    cout<<cnt<<endl;
    }

    林大OJ 912：搜索入门-搜索

    熟能生巧，和上面两道题差不太多！

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

    int dirc[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int n, new_x, new_y;
    char a[5][5];
    struct Point{
    int x,y;
    };
    queue<Point> q;

    void bfs();

    int main()
    {
    ios::sync_with_stdio(false);
    cin>>n;
    while(n–)
    {
    for(int i = 0; i < 4; i++)
    cin>>a[i];
    bfs();
    }
    return 0;
    }

    void bfs()
    {
    q.push({0, 0});
    a[0][0] = '*';
    while(!q.empty())
    {
    Point tmp = q.front();
    q.pop();
    if(tmp.x == 3 && tmp.y == 3)
    {
    cout<<"YES"<<endl;
    return ;
    }
    for(int i=0; i < 4; i++)
    {
    new_x = tmp.x + dirc[i][0];
    new_y=tmp.y + dirc[i][1];
    if(new_x >= 0 && new_x <= 3 && new_y >= 0 &&
    new_y <= 3 && a[new_x][new_y]=='#')
    {
    a[new_x][new_y] = '*';
    q.push({new_x, new_y});
    }
    }
    }
    cout<<"NO"<<endl;
    }

    林大OJ 1214：逃出迷宫-搜索

    这道题由于火堆个数是不确定的，所以这种写法被pass掉了

    void find_fire()
    {
    for(int i = 0; i < R; i++)
    for(int j = 0; j < C; j++)
    if(a[i][j] == 'F')
    {
    a[i][j]='#';
    fire_x = i;
    fire_y = j;
    return ;
    }
    }

    我看了一些算法的书，发现火堆应该用多源bfs，我们先定义一个数组fire_time来存储每个点啥时候烧着,刚开始把每个点都设成无穷大，表示这个位置不会被火烧到，接着将小明入队，逐层移动，每一步都判断小明下一步到达目标位置的时间 < 该位置被点燃的时间（fire_time数组）。若小明 BFS 过程中找到逃出路径，输出最短时间；若队列空仍未逃出，输出IMPOSSIBLE。

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

    int dirc[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    const int INF = 0x3f3f3f3f; // 无穷大，标记未被点燃/未到达

    int T, R, C;
    char a[1005][1005];
    int fire_time[1005][1005];// 记录每个位置被火堆点燃的时间
    int man_time[1005][1005]; // 记录小明到达每个位置的时间

    struct Point{
    int x, y;
    };
    queue<Point> q;

    void fire_bfs() {
    memset(fire_time, INF, sizeof(fire_time));
    while (!q.empty()) q.pop();

    for (int i = 0; i < R; i++) {
    for (int j = 0; j < C; j++) {
    if (a[i][j] == 'F') {
    q.push({i, j});
    fire_time[i][j] = 0;
    }
    }
    }

    // 火堆蔓延BFS
    while (!q.empty()) {
    Point tmp = q.front();
    q.pop();

    for (int i = 0; i < 4; i++) {
    int new_x = tmp.x + dirc[i][0];
    int new_y = tmp.y + dirc[i][1];

    // 条件：不越界、不是墙、未被点燃
    if (new_x >= 0 && new_x < R && new_y >= 0 && new_y < C
    && a[new_x][new_y] != '#' && fire_time[new_x][new_y] == INF)
    {
    fire_time[new_x][new_y] = fire_time[tmp.x][tmp.y] + 1;//记录这个点什么时候被点燃
    q.push({new_x, new_y});
    }
    }
    }
    }

    // 小明BFS
    int man_bfs(int start_x, int start_y) {

    memset(man_time, INF, sizeof(man_time));
    while (!q.empty()) q.pop();

    q.push({start_x, start_y});
    man_time[start_x][start_y] = 0;

    while (!q.empty()) {
    Point tmp = q.front();
    q.pop();

    for (int i = 0; i < 4; i++) {
    int new_x = tmp.x + dirc[i][0];
    int new_y = tmp.y + dirc[i][1];

    // 越界就返回当前时间+1
    if (new_x < 0 || new_x >= R || new_y < 0 || new_y >= C) {
    return man_time[tmp.x][tmp.y] + 1;
    }

    if (a[new_x][new_y] != '#' && man_time[new_x][new_y] == INF //现在这个位置没被点着
    && man_time[tmp.x][tmp.y] + 1 < fire_time[new_x][new_y]) //小明下一步走到这个位置的时间，要比火堆烧到这个位置的时间早
    {
    man_time[new_x][new_y] = man_time[tmp.x][tmp.y] + 1;
    q.push({new_x, new_y});
    }
    }
    }
    return INF;
    }

    int main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while (T–) {
    cin >> R >> C;
    int start_x, start_y;
    for (int i = 0; i < R; i++) {
    cin >> a[i];
    for (int j = 0; j < C; j++) {
    if (a[i][j] == 'J') {
    start_x = i;
    start_y = j;
    }
    }
    }

    fire_bfs();
    int ans = man_bfs(start_x, start_y);

    if (ans == INF) {
    cout << "IMPOSSIBLE" << endl;
    } else {
    cout << ans << endl;
    }
    }
    return 0;
    }

    林大OJ 1693：瓷砖-搜索

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

    int W, H, begin_x, begin_y, cnt, new_x, new_y;
    char a[55][55];
    int dirc[4][2]={{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    struct Point{
    int x,y;
    };
    queue<Point> q;

    void seek_start()
    {
    for(int i = 0; i < H; i++)
    for(int j = 0; j < W; j++)
    if(a[i][j] == '@')
    {
    begin_x = i;
    begin_y = j;
    a[i][j] = '.';
    return;
    }
    }

    void bfs();

    int main()
    {
    ios::sync_with_stdio(false);
    while(cin>>W>>H && (W && H)){
    for(int i=0; i < H; i++)
    cin>>a[i];
    bfs();
    }
    return 0;
    }

    void bfs()
    {
    while(!q.empty())
    {
    q.pop();
    }

    cnt = 0;
    seek_start();
    q.push({begin_x, begin_y});
    a[begin_x][begin_y]='#';
    cnt++;

    while( !q.empty())
    {
    Point tmp = q.front();
    q.pop();
    for(int i=0; i < 4;i++)
    {
    new_x = tmp.x + dirc[i][0];
    new_y = tmp.y + dirc[i][1];
    if(new_x>=0 && new_x<H && new_y>=0 &&
    new_y<W && a[new_x][new_y]=='.')
    {
    a[new_x][new_y] = '#';
    q.push({new_x, new_y});
    cnt++;
    }
    }
    }
    cout<<cnt<<endl;
    }

    赞(0)
    未经允许不得转载：171主机测评 » 2025级大一ACM训练：搜索入门（一）：BFS
    分享到： 更多 (0)
    标签：

    相关推荐

    评论 抢沙发

    取消

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址

    热门标签

    #人工智能(59542)#python(20187)#开发语言(16918)#java(15519)#运维(15397)#linux(14980)#大数据(14611)#服务器(13092)#算法(11810)#前端(10937)#网络(9399)#ai(8954)#数据库(8923)#c++(8192)#课程设计(6817)#学习(6797)#机器学习(6726)#区块链(5928)#OpenClaw(5393)#后端(5172)#spring boot(5019)#深度学习(4967)#c语言(4385)#毕业设计(4300)#数据结构(4207)#安全(4084)#docker(3940)#架构(3880)#javascript(3814)#大模型(3663)

    热门文章

    最新文章

    归档

    分类