BFS小结
代码中常见问题
floodfill:
code1
#include<iostream>
#define x first
#define y second
using namespace std;
const int N = 60, M = N * N;
typedef pair<int, int> PII;
int g[N][N];
//1. 队列可能放所有元素
PII q[M];
bool st[N][N];
int m, n;
int max_area, cnt, sum;
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
void bfs(int x, int y)
{
int hh, tt;
hh = tt = 0;
//2. 加入队列 代表被访问
q[tt ++] = {x, y};
st[x][y] = true;
while(hh < tt){
auto t = q[hh ++];
sum ++;
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 || st[a][b]) continue;
if(g[t.x][t.y] >> i & 1) continue;
//加入队列 代表被访问
q[tt ++] = {a, b};
st[a][b] = true;
}
}
}
int main()
{
cin >> n >> m;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j)
cin >> g[i][j];
}
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
if(!st[i][j]){
sum = 0;
bfs(i, j);
max_area = max(max_area, sum);
cnt ++;
}
}
}
cout << cnt << endl << max_area;
}
code2
#include<iostream>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 1010, M = N * N;
int n;
int g[N][N];
bool st[N][N];
PII q[M];
int peak, valley;
int high, low;
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
void bfs(int x, int y)
{
int hh = 0, tt = 0;
q[tt ++] = {x, y};
st[x][y] = true;
while(hh < tt){
auto t = q[hh ++];
for(int i = 0; i < 8; ++i){
int a = t.x + dx[i], b = t.y + dy[i];
if(a < 0 || a >= n || b < 0 || b >= n) continue;
//3. 判断st[a][b]
if(g[x][y] == g[a][b]){
if(st[a][b]) continue;
q[tt ++] = {a, b};
st[a][b] = true;
}
else if(g[x][y] < g[a][b]) high ++;
else low ++;
}
}
}
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(!st[i][j]){
high = low = 0;
bfs(i, j);
if(!high) peak ++;
if(!low) valley++;
}
}
}
cout << peak << " " << valley;
}
bfs-最长路
code
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int q[N];
int dist[N];
int h[N], e[N], ne[N], idx;
int res = 0;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
bool bfs(int root)
{
int hh, tt;
hh = tt = 0;
q[tt ++] = root;
dist[root] = 1;
while(hh < tt){
int t = q[hh ++];
for(int i = h[t]; i != -1; i = ne[i]){
int k = e[i];
if(dist[k] != -1) return false;
dist[k] = dist[t] + 1;
q[tt ++] = k;
}
}
return true;
}
int main()
{
int n;
cin >> n;
int root = -1;
//1 链表初始化
memset(h, -1, sizeof h);
for(int i = 1; i <= n; ++i){
int k;
cin >> k;
if(k == 0) root = i;
while(k --){
int t;
cin >> t;
add(t, i);
}
}
//2 距离初始化
memset(dist, -1, sizeof dist);
if(root == -1 || !bfs(root)){
cout << -1 << endl;
return 0;
}
//3 找到距离最大值即可
for(int i = 1; i <= n; ++i){
res = max(res, dist[i]);
}
cout << res << endl;
}
最短路
code1
#include<iostream>
#include<cstring>
#define x first
#define y second
using namespace std;
const int N = 1010, M = N * N;
typedef pair<int, int> PII;
int g[N][N];
PII q[M];
//1 pre数组可以起到st数组的作用
PII pre[N][N];
int n;
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
void bfs(int x, int y)
{
int hh, tt;
hh = tt = 0;
//2 加入队列 代表被访问
q[tt ++] = {x, y};
pre[x][y] = {0, 0};
while(hh < tt){
auto t = q[hh ++];
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 >= n || g[a][b] == 1 || pre[a][b].x != -1) continue;
//加入队列 代表被访问
q[tt ++] = {a, b};
pre[a][b] = t;
}
}
}
int main()
{
cin >> n;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j)
cin >> g[i][j];
}
memset(pre, -1, sizeof pre);
//3 倒序搜,正序输出
bfs(n - 1, n - 1);
int a = 0, b = 0, cnt = 0;
while(true)
{
cout << a << " " << b << endl;
if(a == n - 1 && b == n - 1) break;
//4.输出注意:
//错误写法:
//a = pre[a1][b1].x, b = pre[a1][b1].y;
int a1 = a, b1 = b;
a = pre[a1][b1].x;
b = pre[a1][b1].y;
}
return 0;
}
code2