Home Flood Fill
Post
Cancel

Flood Fill

今天 昨天接触了一个叫做 Flood Fill 的算法, 其实就是深搜广搜, 可以不用 vis 记录是否被访问过, 只需要在遍历过后将值修改一下就可以了.

AcWing 1106 山峰和山谷

Link

用 DFS 和 BFS 两种做法:

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
#define f first
#define s second
int n,ans1,ans2;
bool isPeak,isValley;
int w[1010][1010];
int dx[8]={-1,-1,-1,0,1,1,1,0},dy[8]={-1,0,1,1,1,0,-1,-1};
bool v[1010][1010];
void DFS(int x,int y){
    for(int i=0;i<8;++i){
        int tx=x+dx[i],ty=y+dy[i];
        if(tx>=1&&tx<=n&&ty>=1&&ty<=n){
            if(w[tx][ty]==w[x][y]&&!v[tx][ty]){
                v[tx][ty]=true;
                DFS(tx,ty);
            }else if(w[tx][ty]>w[x][y]){
                isPeak=false;
            }else if(w[tx][ty]<w[x][y]){
                isValley=false;
            }
        }
    }
}
void BFS(int x,int y){
    queue<pair<int,int>>q;
    q.push({x,y});
    while(!q.empty()){
        x=q.front().f,y=q.front().s;
        q.pop();
        for(int i=0;i<8;++i){
            int tx=x+dx[i],ty=y+dy[i];
            if(tx>=1&&tx<=n&&ty>=1&&ty<=n){
                if(w[tx][ty]==w[x][y]&&!v[tx][ty]){
                    v[tx][ty]=true;
                    q.push({tx,ty});
                }else if(w[tx][ty]>w[x][y]){
                    isPeak=false;
                }else if(w[tx][ty]<w[x][y]){
                    isValley=false;
                }
            }
        }
    }
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            scanf("%d",&w[i][j]);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            if(!v[i][j]){
                v[i][j]=true;
                isPeak=true,isValley=true;
                // DFS(i,j);
                BFS(i,j);
                if(isPeak) ans1++;
                if(isValley) ans2++;
            }
    printf("%d %d\n",ans1,ans2);
    return 0;
}
This post is licensed under CC BY 4.0 by the author.