学习平台
AcWing 、 LeetCode
💡:模板题、⭐:经典题,类型不太一样、❗:难题,存在不理解
Flood Fill
顾名思义为洪水覆盖法,每次把经过遍历的点看作已经被覆盖的点,然后根据题目要求向周围没有遍历的点扩展即可。
主要是通过bfs
求解是否连通问题。当然也可以求解连通图的数量或者大小,只需要进行变形即可。
为什么从一个点开始遍历使用bfs
遍历到目标节点时,即为最短距离:
队列的性质:两段性 (例如数的的层序遍历,队列中最多只存相邻两层中的元素)、单调性
题目1:池塘计数 💡
池塘计数
思路
本题为八连通问题,即一个点的连通点有八个方向,因此可以使用双重for
循环遍历这八个点,特别注意,需要将自己”扣掉“。
本题的属性是:数量,即为计算连通区域的数量。因此状态数组st[][]
使用bool
类型即可
需要用到的数组:
g[][]
:保存原来的地图
q[][]
:pair<int, int>
类型数组,主要用于模拟队列,每次遍历一个点,将该点的横纵坐标存入队列中。
st[][]
:状态数组,用来记录某个位置的点是否被遍历过。
题解
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
| #include <iostream> #include <algorithm>
#define x first #define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010; int n, m; char g[N][N]; PII que[N * N]; bool used[N][N];
void bfs(int sx, int sy) { int hh = 0, tt = 0; que[0] = {sx, sy}; used[sx][sy] = true; while(hh <= tt) { PII t = que[hh ++]; for(int i = t.x - 1; i <= t.x + 1; i ++) for(int j = t.y - 1; j <= t.y + 1; j ++){ if(i == t.x && j == t.y) continue; if(i < 0 || i >= n || j < 0 || j >= m) continue; if(g[i][j] == '.' || used[i][j]) continue; que[++ tt] = {i, j}; used[i][j] = true; } } }
int main() { scanf("%d%d", &n, &m); for(int i = 0; i < n; i ++) scanf("%s", g[i]); int cnt = 0; for(int i = 0; i < n; i ++) for(int j = 0; j < m; j ++) if(g[i][j] == 'W' && !used[i][j]) { bfs(i, j); cnt ++; } cout << cnt << endl; return 0; }
|
- 时间复杂度:O(n a b ),其中 n 是数据的组数,a 是每组数据的行数,b 是每组数据的列数
- 空间复杂度:O(n * n),模拟队列最坏情况存放所有的点
执行用时:328 ms
内存消耗:7392 KB
通过测试用例:10/10 个数据
题目2:城堡问题
城堡问题
思路
求房间总数的思路和【池塘计数】完全相同,本题为4连通问题。输出最大房间的面积,每次出队则当前房间面积+1。取最大值即可。
题解
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
| #include <cstring> #include <iostream> #include <algorithm>
#define x first #define y second
using namespace std; typedef pair<int, int> PII;
const int N = 55, M = N * N; int n, m; int g[N][N]; PII q[M]; bool st[N][N];
int bfs(int sx, int sy) { int dx[4] = {0, -1, 0, 1}; int dy[4] = {-1, 0, 1, 0}; int hh = 0, tt = 0; int area = 0; q[0] = {sx, sy}; st[sx][sy] = true; while(hh <= tt) { PII 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 >= m || b < 0 || b >= n) continue; if(st[a][b]) continue; if(g[t.x][t.y] >> i & 1) continue; q[++ tt] = {a, b}; st[a][b] = true; } } return area; }
int main() { cin >> m >> n; for(int i = 0; i < m; i ++) for(int j = 0; j < n; j ++) { cin >> g[i][j]; } int cnt = 0, maxs = 0; for(int i = 0; i < m; i ++) for(int j = 0; j < n; j ++) if(!st[i][j]){ maxs = max(maxs, bfs(i, j)); cnt ++; } cout << cnt << endl; cout << maxs << endl; return 0; }
|
- 时间复杂度:O(n a b ),其中 n 是数据的组数,a 是每组数据的行数,b 是每组数据的列数
- 空间复杂度:O(n * n),模拟队列最坏情况存放所有的点
执行用时:328 ms
内存消耗:7392 KB
通过测试用例:10/10 个数据