1106. 山峰和山谷(bfs--flood fill)(c++详解)(优化)_c++题目山峰和山谷

题目描述:
FGD小朋友特别喜欢爬山，在爬山的时候他就在研究山峰和山谷。为了能够对旅程有一个安排，他想知道山峰和山谷的数量。给定一个地图，为FGD想要旅行的区域，地图被分为 n×n 的网格，每个格子 (i,j) 的高度 w(i,j) 是给定的。若两个格子有公共顶点，那么它们就是相邻的格子，如与 (i,j) 相邻的格子有(i−1,j−1),(i−1,j),(i−1,j+1),(i,j−1),(i,j+1),(i+1,j−1),(i+1,j),(i+1,j+1)。
我们定义一个格子的集合 S 为山峰（山谷）当且仅当：

你的任务是，对于给定的地图，求出山峰和山谷的数量，如果所有格子都有相同的高度，那么整个地图即是山峰，又是山谷。

输入格式
第一行包含一个正整数 n，表示地图的大小。

接下来一个 n×n 的矩阵，表示地图上每个格子的高度 w。

输出格式
共一行，包含两个整数，表示山峰和山谷的数量。

数据范围
1≤n≤1000,
0≤w≤1e9


思路:本题就是一直搜索,寻找山峰和山谷,山峰就是所有的数一样而且周围没有比它高的点,所有我们可以用a来表示,一旦周围有比你高的,那就不可能是山峰,直接a=true,我们让a=0的时候peak++,同理,用b=0的时候valley++,只要有比你低的点,你就不可能是山峰.
这个方法的优点是可以有效的避开寻找一样的数字的麻烦,因为如果这一片所谓的"山峰"或者"山谷"出现的不一样的数字,那么就一定会出现一个大一个小的情况,从何使得a=b=true,直接可以排除这种情况,可以不用单独判断是否相等了省去了思考和写过多代码的麻烦,废话不说**,
上代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define x first
#define y second
using namespace std ;
const int N=1050;
typedef pair<int,int> PII;//方便存点
int n;
int g[N][N];//存图
bool st[N][N];//标记是否检查过该点
bool a,b;
int dx[8] ={0,0,1,1,1,-1,-1,-1};
int dy[8] ={1,-1,1,0,-1,1,0,-1};//这个要注意
//是八个方向,别用四个方向了
int bfs(int x,int y)
{
    queue<PII>q;
    q.push({x , y});//插入队列
    st[x][y] = true ;
    while(q.size())
    {
        auto t=q.front() ;
        q.pop();
        for(int i=0;i<8;i++)
        {
            int xx=t.x+dx[i],yy=t.y+dy[i];
         if(xx < 0 || xx >= n || yy < 0 || yy >= n) continue;
         if(g[xx][yy]>g[t.x][t.y]) a=true;
         //代表周围出现了比当前的高的地方,也就是说明:当前不可能是山峰
         else if(g[xx][yy]<g[t.x][t.y]) b=true;
         //代表周围出现了比当前的低的地方,也就是说明:当前不可能是山谷
         else
         //说明这个平面是山谷或者山峰,还没有判断出来
            {
                if(!st[xx][yy])
                {
                    st[xx][yy]=true;//标记一下
                    q.push({xx,yy});//继续搜索
                }
            }
        }
    }
}
int main()
{
    cin>>n;
    int peak=0,valley=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>g[i][j];
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {
            if(!st[i][j])
            {
                a=b=0;
                bfs(i,j);
                if(a && !b) valley++ ;
                else if(!a && b) peak++ ;
                else if(!a && !b) peak++ , valley++ ;
            }
        }
    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