Luogu

算法

这题就是Dfs大水题。
先把每个联通块求出来,同时判断周围一圈的高度情况,用一个全局变量传下去就行了。
注意周围既有比它高又有比它低是什么都不算的。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

const int dx[8]={-1,-1,-1,0,0,1,1,1};
const int dy[8]={-1,0,1,-1,1,-1,0,1};
const int N=1000+10;

int a[N][N];
bool vis[N][N];
int n,type=0; //type为1则为山谷,为2则为山峰,为-1则什么都不是 

inline int Dfs(int x,int y) {
    for (re int i=0;i<8;i++) {
        int X=x+dx[i],Y=y+dy[i];
        if (X<1||X>n||Y<1||Y>n) continue;
        if (a[X][Y]==a[x][y]&&!vis[X][Y]) {
            vis[X][Y]=1;
            Dfs(X,Y);
        }
        else if ((a[X][Y]<a[x][y]&&type==1)||(a[X][Y]>a[x][y]&&type==2)) type=-1;
        else if (!type) {
             if (a[X][Y]<a[x][y]) type=2;
             else if (a[X][Y]>a[x][y]) type=1;
        }
    }
}

int main() {
    scanf("%d",&n); bool all_same=1;
    for (re int i=1;i<=n;i++)
        for (re int j=1;j<=n;j++) {
            scanf("%d",&a[i][j]);
            if (a[i][j]!=a[1][1]) all_same=0;
        }
    if (all_same) { printf("1 1\n"); return 0; }
    int sg=0,sf=0;
    for (re int i=1;i<=n;i++)
        for (re int j=1;j<=n;j++) {
             if (!vis[i][j]) {
                 type=0; vis[i][j]=1; Dfs(i,j);
                 if (type==1) sg++;
                 else if (type==2) sf++;
             }
        }
    printf("%d %d\n",sf,sg);
    return 0;
}
最后修改:2019 年 05 月 26 日 02 : 29 PM