GRZ山峰和山谷

Description

　　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为山峰（山谷）当
且仅当：1.S的所有格子都有相同的高度。2.S的所有格子都联通3.对于s属于S，与s相邻的s’不属于S。都有ws >
ws’（山峰），或者ws < ws’（山谷）。你的任务是，对于给定的地图，求出山峰和山谷的数量，如果所有格子
都有相同的高度，那么整个地图即是山峰，又是山谷。

Input

　　第一行包含一个正整数n，表示地图的大小（1<=n<=1000）。接下来一个n*n的矩阵，表示地图上每个格子的高
度。(0<=w<=1000000000)

Output

　　应包含两个数，分别表示山峰和山谷的数量。

Sample Input

输入样例1
5
8 8 8 7 7
7 7 8 8 7
7 7 7 7 7
7 8 8 7 8
7 8 8 8 8
输入样例2
5
5 7 8 3 1
5 5 7 6 6
6 6 6 2 8
5 7 2 5 8
7 1 0 1 7

Sample Output

输出样例1
2 1
输出样例2
3 3

　　分析：

　　很显然的广搜，但是一开始想复杂了，然后T了几个点。。翻了下博客，原来直接BFS就行了。。。真傻。。。

　　每次对于一个还未搜索过的点进行广搜，如果遇到高度相同的点就放进队列中，如果遇到高度不同的点就记录然后判断该区域是山谷还是山顶，有些小细节也需要注意。（看网上大佬们的博客说这好像叫什么Floodfill算法。。蒟蒻完全母鸡，瑟瑟发抖。。。）

　　Code：

//It is made by HolseLee on 6th Aug 2018

//BZOJ1102

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<iostream>

#include<iomanip>

#include<algorithm>

#include<queue>

using namespace std;

const int N=;

int n,a[N][N],ans1,ans2;

int mi[]={,-,,,,-,,-},mj[]={,,,-,,-,-,};

bool vis[N][N];

struct Node{

    int x,y;

    Node(int xx=,int yy=){

        x=xx,y=yy;

    }

};

queue<Node>team;

inline int read()

{

    char ch=getchar();int num=;bool flag=false;

    while(ch<''||ch>''){if(ch=='-')flag=true;ch=getchar();}

    while(ch>=''&&ch<=''){num=num*+ch-'';ch=getchar();}

    return flag?-num:num;

}

inline void bfs(int x,int y)

{

    int high=,low=;

    while(!team.empty())team.pop();

    team.push(Node{x,y});

    vis[x][y]=true;

    Node now;

    while(!team.empty()){

        now=team.front();team.pop();

        x=now.x,y=now.y;

        for(int i=;i<;++i)

        if(x+mi[i]>=&&x+mi[i]<=n&&y+mj[i]>=&&y+mj[i]<=n){

            if(a[x+mi[i]][y+mj[i]]==a[x][y]&&!vis[x+mi[i]][y+mj[i]]){

                team.push(Node{x+mi[i],y+mj[i]});

                vis[x+mi[i]][y+mj[i]]=true;

            }

            if(a[x+mi[i]][y+mj[i]]>a[x][y])++low;

            if(a[x+mi[i]][y+mj[i]]<a[x][y])++high;

        }

    }

    if(high&&!low)ans1++;

    if(!high&&low)ans2++;

}

int main()

{

    n=read();

    int last=;bool flag=false;

    for(int i=;i<=n;++i)

    for(int j=;j<=n;++j)

        a[i][j]=read();

    memset(vis,,sizeof(vis));

    for(int i=;i<=n;++i)

    for(int j=;j<=n;++j)

    if(!vis[i][j])bfs(i,j);

    if(!ans1&&!ans2)printf("1 1\n");

    else printf("%d %d\n",ans1,ans2);

    return ;

}