acwing算法提高之搜索--BFS中的Flood Fill和最短路模型

本文主要是介绍acwing算法提高之搜索--BFS中的Flood Fill和最短路模型，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1 专题说明

本专题用来记录使用Flood Fill算法和最短路模型解决的搜索问题。

2 训练

题目1：1097池塘计数

C++代码如下，
方法1：使用bfs算法

#include <iostream>
#include <queue>using namespace std;const int N = 1010;int n, m;
char g[N][N];
bool st[N][N];void bfs(int i, int j) {queue<pair<int,int>> q;q.push(make_pair(i, j));st[i][j] = true;while (!q.empty()) {pair<int,int> t = q.front();q.pop();int x = t.first, y = t.second;for (int dx = -1; dx <= 1; ++dx) {for (int dy = -1; dy <= 1; ++dy) {if (dx == 0 && dy == 0) continue;int nx = x + dx, ny = y + dy;if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;if (st[nx][ny]) continue;if (g[nx][ny] != 'W') continue;q.push(make_pair(nx, ny));st[nx][ny] = true;}}        }return;
}int main() {cin >> n >> m;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {cin >> g[i][j];}}int res = 0;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (g[i][j] == 'W' && st[i][j] == false) {bfs(i, j);res++;}}}cout << res << endl;return 0;
}

方法2：使用并查集

#include <iostream>
#include <vector>using namespace std;const int N = 1010;
const int M = 1e6 + 10;int n, m;
char g[N][N];int p[M];
int cnt;int find(int x) {if (p[x] != x) p[x] = find(p[x]);return p[x];
}void merge(int a, int b) {int pa = find(a);int pb = find(b);if (pa == pb) return;p[pa] = pb;cnt--;return;
}int main() {cin >> n >> m;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {cin >> g[i][j];if (g[i][j] == 'W') cnt++;}}//并查集初始化for (int k = 0; k < n * m; ++k) {p[k] = k;}int dirs[8][2] = {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1}};for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (g[i][j] == 'W') {for (int k = 0; k < 8; ++k) {int x = i + dirs[k][0];int y = j + dirs[k][1];if (x < 0 || x >= n || y < 0 || y >= m) continue;if (g[x][y] != 'W') continue;int a = i * m + j; //乘以列数int b = x * m + y;merge(a, b);}}}}cout << cnt << endl;return 0;
}