POI：山峰和山谷Grz

题目分析：

  • 八连通的所有格子为联通块
  • 如果都有ws > ws'，表示山谷,若都有ws < ws',则表示山峰

代码如下：

#include<iostream>
#include<queue>

using namespace std;

#define x first
#define y second
#define pii pair<int,int>
#define el endl

const int N = 1e3 + 10;

int n;
int g[N][N];
bool st[N][N];

void bfs(int sx,int sy,bool& is_a,bool& is_b){
    queue<pii> q;
    q.push({sx,sy});
    st[sx][sy] = true;
    while(q.size()){
        pii t = q.front();
        q.pop();

        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 - 1 || j < 0 || j > n - 1) continue;
                if(g[i][j] != g[t.x][t.y]){
                    if(g[i][j] > g[t.x][t.y]) is_a = true;
                    else is_b = true;    
                }else if(!st[i][j]){
                    st[i][j] = true;
                    q.push({i,j});
                }
            }
    }
}
int main(){
    cin >> n;
    for(int i = 0; i < n; i ++ )
        for(int j = 0; j < n; j ++ )
            cin >> g[i][j];
    int a = 0, b = 0;
    for(int i = 0; i < n; i ++ )
        for(int j = 0; j < n; j ++ )
            if(!st[i][j]){
                bool is_a = false,is_b = false;
                bfs(i,j,is_a,is_b);
                if(!is_a) a ++;
                if(!is_b) b ++;
            }
    cout<<a<<" "<<b;    
    return 0;
}