在 \(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