0%

算法提高课 - 搜索

学习平台

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; // hh队头指针,tt队尾指针
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 ++) // 遍历3 * 3的区间范围
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
// 1西,2北,4东,8南
#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]; // [a][b]分别是上下左右是个房间

if(a < 0 || a >= m || b < 0 || b >= n) continue; // 越界
if(st[a][b]) continue; // 位置为0,或者已经被遍历过了
if(g[t.x][t.y] >> i & 1) continue; // 第i个位置为墙

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; // cnt:连通块个数,maxs:最大面积

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 个数据

正在加载今日诗词....