P3456 [POI2007]GRZ-Ridges and Valleys（bfs）

P3456 [POI2007]GRZ-Ridges and Valleys

八个方向都跑一遍bfs，顺便判断一下是山峰还是山谷，或者是山坡（俩都不是）

（实在不知道要说啥了qwq）

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cctype>

#include<queue>

using namespace std;

inline int Int(){

    char c=getchar(); int x=;

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();

    return x;

}

int d1[]={,,,-,,,-,-};

int d2[]={,,-,,,-,,-};

int n,a[][],ridge,valley;

bool vis[][];

struct data{int x,y;};

inline void bfs(data f){

    queue <data> h; h.push(f);

    int p=-; vis[f.x][f.y]=; //p:该处的状态

    while(!h.empty()){

        data u=h.front(); h.pop();

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

            int r1=u.x+d1[i],r2=u.y+d2[i];

            if(r1<||r1>n||r2<||r2>n) continue;

            if(a[u.x][u.y]!=a[r1][r2]){

                if(p==-) p=(a[u.x][u.y]>a[r1][r2]);

                else p= p==(a[u.x][u.y]>a[r1][r2]) ? p:;

                continue; //直接写成这样方便（逃

            }

            if(!vis[r1][r2]) vis[r1][r2]=; //标记记得打

            else continue;

            h.push((data){r1,r2});

        }

    }

    if(p==-) ++ridge,++valley; //整个图都是一块相同海拔的

    else if(p==) ++valley;

    else if(p==) ++ridge;

}

int main(){

    n=Int();

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

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

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

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

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

            if(!vis[i][j])

                bfs((data){i,j});

    printf("%d %d",ridge,valley);

    return ;

}