首页 > 其他分享 >bfs判重的坑

bfs判重的坑

时间:2024-03-17 23:34:01浏览次数:26  
标签:node 判重 int st bfs ++ include

在 \(bfs\) 中判重时,应优先在入队时进行判重,而不是在出队时进行判重,因为一个节点 \(u\) 在入队到出队的过程中,可能需要先出队很多其他节点 \(v\),这就会导致其他节点出队且加入新节点的过程中,可能会重复加入多次节点 \(u\),进而导致 \(queue\) 占用的空间过大,最后可能有几个点 \(MLE(Memory Limit Excess)\)。

例题
AC代码:在出队时判重

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

using namespace std;

const int N = 40;

int n;
int g[N][N];
bool st[N][N];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

void bfs(int fx, int fy)
{
    typedef pair<int,int> PII;
    bool is_bound = false;
    queue<PII> q;
    vector<PII> node;
    q.push({fx, fy});
    st[fx][fy] = true;  // enqueue check
    while(q.size())
    {
        auto [x, y] = q.front();    q.pop();
        node.push_back({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 >= n)
            {
                is_bound = true;
                continue;
            }
            if(g[a][b] || st[a][b]) continue;
            q.push({a, b});
            st[a][b] = true; // enqueue check
        }
    }
    if(!is_bound)
        for(auto [a, b] : node)
            g[a][b] = 2;
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++ )    
        for(int j = 0; j < n; j ++ )    cin >> g[i][j];
    
    for(int i = 0; i < n; i ++ )
        for(int j = 0; j < n; j ++ )
            if(!g[i][j] && !st[i][j])
                bfs(i, j);
    
    for(int i = 0; i < n; i ++ )    
        for(int j = 0; j < n; j ++ )    cout << g[i][j] << " \n"[j == n - 1];
        
    return 0;
}

MLE代码:出队时判重

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

using namespace std;

const int N = 40;

int n;
int g[N][N];
bool st[N][N];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

void bfs(int fx, int fy)
{
    typedef pair<int,int> PII;
    bool is_bound = false;
    queue<PII> q;
    vector<PII> node;
    q.push({fx, fy});
    while(q.size())
    {
        auto [x, y] = q.front();    q.pop();
        node.push_back({x, y});
        st[x][y] = true;    // dequeue check
        for(int i = 0; i < 4; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= n)
            {
                is_bound = true;
                continue;
            }
            if(g[a][b] || st[a][b]) continue;
            q.push({a, b});
        }
    }
    if(!is_bound)
        for(auto [a, b] : node)
            g[a][b] = 2;
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++ )    
        for(int j = 0; j < n; j ++ )    cin >> g[i][j];
    
    for(int i = 0; i < n; i ++ )
        for(int j = 0; j < n; j ++ )
            if(!g[i][j] && !st[i][j])
                bfs(i, j);
    
    for(int i = 0; i < n; i ++ )    
        for(int j = 0; j < n; j ++ )    cout << g[i][j] << " \n"[j == n - 1];
        
    return 0;
}

标签:node,判重,int,st,bfs,++,include
From: https://www.cnblogs.com/ALaterStart/p/18079424

相关文章

  • 图论:DFS与BFS
    目录1.DFS(图论)1.1.DFS过程1.2.应用2.BFS(图论)2.1.BFS过程2.2.应用2.3.双端队列BFS实现2.4.优先队列BFS(堆优化Dijkstra算法)1.DFS(图论)DFS全称是,中文名是深度优先搜索,是一种用于遍历或搜索树或图的算法。所谓深度优先,就是说每次都尝试向更深的节点走。广义上的DFS:DF......
  • 【BFS二叉树】113路径总和II
    113路径总和II给你二叉树的根节点root和一个整数目标和targetSum,找出所有从根节点到叶子节点路径总和等于给定目标和的路径。思路:题目最终输出的是路径,因此用BFS遍历的时候,需要记录走到每个节点的路径;又因为路径和是要等于某个目标值的,因此也需要记录目标和。⇒......
  • 广度优先搜索(BFS)在数据结构中的应用
    广度优先搜索(BreadthFirstSearch,简称BFS)是图论中最基本的搜索算法之一,它用于遍历或搜索给定的图形结构,如树或图。与深度优先搜索(DFS)相比,BFS以广度优先的方式逐层探索节点,即它会先访问离起始节点近的所有节点,再逐步访问离起始节点远的节点。算法原理BFS算法的核心思想是使用队......
  • DFS判重问题
    奇怪的电梯(洛谷)题目背景感谢@yummy提供的一些数据。题目描述呵呵,有一天我做了一个梦,梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯,而且第\(i\)层楼(\(1\lei\leN\))上有一个数字\(K_i\)(\(0\leK_i\leN\))。电梯只有四个按钮:开,关,上,下。上下的层数等于当前楼层上......
  • 面试官:如何实现10亿数据判重?
    From: https://mp.weixin.qq.com/s/l2yVtL5siHpxzNLuxJ3nkQ当数据量比较大时,使用常规的方式来判重就不行了。例如,使用MySQL数据库判重,或使用List.contains()或Set.contains()判重就不可行,因为MySQL在数据量大时查询就会非常慢,而数据库又是及其珍贵的全局数据库资源。......
  • 深度优先搜索DFS、广度优先搜索BFS
    深度优先搜索DFS基本概念深度优先搜索(Depth-FirstSearch,DFS)是十分常见的图搜索方法之一。深度优先搜索会沿着一条路径一直搜索下去,在无法搜索时,回退到刚刚访问过的节点。它从初始节点出发,按预定的顺序扩展到下一个节点,然后从下一节点出发继续扩展新的节点,不断递归执行这个过......
  • 面试官:如何实现10亿数据判重?
    当数据量比较大时,使用常规的方式来判重就不行了。例如,使用MySQL数据库判重,或使用List.contains()或Set.contains()判重就不可行,因为MySQL在数据量大时查询就会非常慢,而数据库又是及其珍贵的全局数据库资源。《阿里巴巴Java开发手册》上也说了,如果单表数据量超过500万......
  • 补基础题(BFS)
    P1135奇怪的电梯-洛谷|计算机科学教育新生态(luogu.com.cn)#include<iostream>#include<queue>#include<cstring>usingnamespacestd;constintN=210;intK[N],n,A,B,vis[N];structnode{intnow,step;};#definecheck(a)(a>=1&&a<=n......
  • Poj 1077 Eight!(BFS模板解法)
    吃完晚饭,啃着tomato来poj上提交,结果不支持unordered_map,吐血啦,看来还是要用BFS+康托展开,还想再写一篇双向BFS的,对这道题算是圆满了*_*,但是要用G++提交,C++会报错我也不知道为嘛#include<iostream>#include<cstring>#include<queue>#include<unordered_map>usingnamespaces......
  • Poj 1077 Eight!(BFS-A*)
    1077--Eight(poj.org)由结论可以知道逆序对为奇数的时候无解,f为估值函数,计算曼哈顿距离。想用康托展开写,但多状态数码问题用数组存储状态不够,有TLE的风险,还是A*吧!吃一个tomato宣告今日...不知道结不结束#include<iostream>#include<vector>#include<queue>#include......