文章目录
前言
一、Flood Fill
二、例题，代码
AcWing 1097. 池塘计数
本题分析
AC代码
AcWing 1098. 城堡问题
本题分析
AC代码
AcWing 1106. 山峰和山谷
本题分析
AC代码
三、时间复杂度
前言
复习acwing算法提高课的内容，本篇为讲解算法：Flood Fill，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、Flood Fill
Flood Fill算法是搜索的算法中的一种，用来解决类似田地覆盖这么一系列问题，算法核心是BFS
二、例题，代码
AcWing 1097. 池塘计数
本题链接：AcWing 1097. 池塘计数
本博客提供本题截图：
本题分析
本题就是水的覆盖问题，可以用bfs去解，核心思路就是从第一行第一列（即图中的第一个元素）去遍历，这里需要一个bool st[N][N]数组去记录这个点有没有被遍历过，如果被遍历过的话直接跳过这个点就可以了，我们每次挑选合适的点放入到队列之中，并用这个点作为“母点”去向8个方向去扩散，这里扩散的时候没有使用向量的方法，对于四扩散向量的方法很简单，但是对于8个方向的扩散，显然这里用一个二重for循环可以比较容易的解决问题，注意特判for循环中的条件，对于不符合条件的点continue
if (t.x == i && t.y == j) continue; //遍历到这个点的时候continue if (i < 0 || i >= n || j < 0 || j >= m) continue; //越界的时候continue if (g[i][j] == '.' || st[i][j]) continue; //这个点如果不是水的话或者这个点之前被遍历过的话就continue
这样三个if判断之后的点一定是符合题意可以扩散水的点，那么就把这个点放到队列中，并把这个点的bool值变成true
q[++ tt] = {i, j}; st[i][j] = true;
AC代码
#include <cstdio> #include <algorithm> #include <map> #define x first #define y second using namespace std; typedef pair<int, int> PII; const int N = 1010, M = N * N; PII q[M]; char g[N][N]; bool st[N][N]; int n, m, cnt; void bfs(int x1, int y1) { int hh = 0, tt = 0; q[0] = {x1, y1}; st[x1][y1] = true; while (hh <= tt) { auto t = q[hh ++]; for (int i = t.x - 1; i <= t.x + 1; i ++ ) for (int j = t.y - 1; j <= t.y + 1; j ++ ) { if (t.x == i && t.y == j) continue; if (i < 0 || i >= n || j < 0 || j >= m) continue; if (g[i][j] == '.' || st[i][j]) continue; q[++ tt] = {i, j}; st[i][j] = true; } } } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i ++ ) scanf("%s", g[i]); for (int i = 0; i < n; i ++ ) for (int j = 0; j < m; j ++ ) if (!st[i][j] && g[i][j] == 'W') { bfs(i, j); cnt ++; } printf("%d", cnt); return 0; }
AcWing 1098. 城堡问题
本题链接：AcWing 1098. 城堡问题
本博客提供本题截图：
本题分析
和上一个题目基本一致，不同的有两点，一点是上一个题是八扩散，用的是两重for循环，这个题是四扩散，用的是向量，第二个不同是如何把数字形象化：位运算。
AC代码
#include <cstdio> #include <map> #include <algorithm> #define x first #define y second using namespace std; typedef pair<int, int> PII; const int N = 55, M = N * N; PII q[M]; int g[N][N]; bool st[N][N]; int n, m; int bfs(int x1, int y1) { int area = 0; int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0}; int hh = 0, tt = 0; q[0] = {x1, y1}; st[x1][y1] = true; while (hh <= tt) { auto t = q[hh ++]; area ++; 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) continue; if (g[t.x][t.y] >> i & 1) continue; if (st[a][b]) continue; q[++ tt] = {a, b}; st[a][b] = true; } } return area; } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i ++ ) for (int j = 0; j < m ; j ++ ) scanf("%d", &g[i][j]); int cnt = 0, area = 0; for (int i = 0; i < n; i ++ ) for (int j = 0; j < m; j ++ ) if (!st[i][j]) { cnt ++; area = max (area, bfs(i, j)); } printf("%d\n%d\n", cnt, area); return 0; }
