Acwing算法提高课—搜索_为什么网上找不到acwing的课

BFS

Flood Fill

AcWing 1097. 池塘计数

/*
基础课回忆：
搜索：DFS BFS
BFS：
    最短距离(AcWing 844. 走迷宫)：给一个地图(二维矩阵)，定义起点终点，问从起点走到终点的最短距离
    最小步数(AcWing 845. 八数码)：对地图本身操作，求其中一种状态(地图)变成另外一种地图的最小步数，把整个地图看成一个点
BFS特点：
    1.求最小
    2.基于迭代，不会爆栈(相对于DFS，当一个问题层数很深，但节点个数不深，优先选择BFS)
    
Flood Fill算法：可以在线性时间复杂度内，找到某个点所在的连通块

地图连通有两种：四连通，八连通
*/
#include <cstring>
#include <iostream>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1010, M = N * N;

int n, m;
char g[N][N];
PII q[M];//用Flood Fill算法遍历二维地图，一般都要存下标
bool st[N][N];//宽搜都需要判重，标记数组，防止重复遍历某个点

void bfs(int sx, int sy)
{
    int hh = 0, tt = 0;//数组模拟队列
    q[0] = {sx, sy};
    st[sx][sy] = true;

    while (hh <= tt)
    {
        PII 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 (i == t.x && j == t.y) 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()
{
    cin>>n>>m;//读入数据较大，推荐用scanf读
    for (int i = 0; i < n; i ++ ) cin>>g[i];//读入每一行

    int cnt = 0;//池塘数目
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            if (g[i][j] == 'W' && !st[i][j])//宽搜判断条件一般都很长，想清楚
            {
                bfs(i, j);//输入起点
                cnt ++ ;
            }

    cout<<cnt<<endl;

    return 0;
}
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
64
65
66
67
68
69
70
71
72
73

AcWing 1098. 城堡问题

/*
找到所有连通块：Flood Fill  
但是输入比较复杂，依次输入每个小方块周围墙的情况，可以用二进制编码表示，判断第0到3位哪一位为1
*/
#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}, 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 ++ )
        {
        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]==false&&!(g[t.x][t.y]>>i&1)){
                q[++tt]={a,b};
                st[a][b]=true;
            }
            // if (a < 0 || a >= n || b < 0 || b >= m) continue;
            // if (st[a][b]) continue;
            // if (g[t.x][t.y] >> i & 1) continue;//二进制表示第i位是否为1

            // q[ ++ tt] = {a, b};
            // st[a][b] = true;
        }
        }
    }

    return area;
}

int main()
{
    cin >> n >> m;//输入较少，cin
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            cin >> 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])
            {
                area = max(area, bfs(i, j));
                cnt ++ ;
            }

    cout << cnt << endl;
    cout << area << endl;

    return 0;
}
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

AcWing 1106. 山峰和山谷

/*
八连通，统计连通块与周围关系
*/
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=1010;

#define x first
#define y second
typedef pair<int,int> PII;

int n;
int h[N][N];
PII q[N*N];
bool st[N][N];

void bfs(int sx,int sy,bool& has_higher,bool& has_lower){
    int hh=0,tt=0;
    q[0]={sx,sy};
    st[sx][sy]=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(i==t.x&&j==t.y) continue;
                if(i<0||i>=n||j<0||j>=n) continue;
                if(h[i][j]!=h[t.x][t.y]){// 山脉的边界
                    if(h[i][j]>h[t.x][t.y]) has_higher=true;
                    else has_lower=true;
                }
                else if(!st[i][j]){
                    q[++tt]={i,j};
                    st[i][j]=true;
                }
            }
        }
    }
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>h[i][j];
        }
    }
    
    int peak=0,valley=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(!st[i][j]){
                //统计当前格子所在连通块与周围格子的关系，两个变量为周围是否有比它高或低的，只有为false时才能完全确定周围没有比它高或低的
                bool has_higher=false,has_lower=false;
                bfs(i,j,has_higher,has_lower);//同一个山脉可能既是山峰又是山谷，所以都要判断
                if(!has_higher) peak++;
                if(!has_lower) valley++;//别加else，这样就2选1了
            }
        }
    }
    
    cout<<peak<<' '<<valley<<endl;
    return 0;
}
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
64
65
66
67
68
69

最短路模型

AcWing 1076. 迷宫问题

/*
当所有边权重相等时，用宽搜从起点开始搜就可以得到所有点的单元最短路
走迷宫题目扩展，不止要求出最短路长度，还要求出方案路径
*/
#include <cstring>
#include <iostream>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1010, M = N * N;

int n;
int g[N][N];
PII q[M];
PII pre[N][N];//从st数组扩展而来，保存每一个格子从哪儿走过来的

void bfs(int sx, int sy)
{
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    int hh = 0, tt = 0;
    q[0] = {sx, sy};

    memset(pre, -1, sizeof pre);
    pre[sx][sy] = {0, 0};
    while (hh <= tt)
    {
        PII 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) continue;
            if (g[a][b]) continue;
            if (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];
        }
    }
    
    bfs(n-1,n-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