分析

• 在floodfill的同时记录每个连通块周围是否有高于或者低于当前连通块的山峰，根据这个就可以判断山峰山谷的个数。

BFS

// BFS
#include <iostream>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1010, M = N * N;

int n;
int h[N][N];
PII q[M];
bool st[N][N];

void bfs(int sx, int sy, int &has_higher, int &has_lower) {

    int hh = 0, tt = 0;
    q[0] = {sx, sy};
    st[sx][sy] = true;

    while (hh <= tt) {
        PII t = q[hh++];

        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 || j < 0 || j >= n) continue;
                if (h[t.x][t.y] != h[i][j]) {
                    if (h[i][j] > h[t.x][t.y]) has_higher = true;
                    else has_lower = true;
                } else if (!st[i][j]) {
                    q[++tt] = {i, j};
                    st[i][j] = true;
                }
            }
    }
}

int main() {

    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &h[i][j]);

    int peak = 0, valley = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j< n; j++)
            if (!st[i][j]) {
                int has_higher = false, has_lower = false;
                bfs(i, j, has_higher, has_lower);
                if (!has_higher) peak++;
                if (!has_lower) valley++;
            }

    printf("%d %d\n", peak, valley);

    return 0;
}

dfs

// DFS
// 没有通过，原因：Memory Limit Exceeded
#include <iostream>

#define x first
#define y second

using namespace std;

const int N = 1010;

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

void dfs(int sx, int sy, int &has_higher, int &has_lower) {

    st[sx][sy] = true;
    for (int i = sx - 1; i <= sx + 1; i++)
        for (int j = sy - 1; j <= sy + 1; j++) 
            if (i >= 0 && i < n && j >= 0 && j < n) {
                if (h[i][j] != h[sx][sy]) {
                    if (h[i][j] > h[sx][sy]) has_higher = true;
                    else has_lower = true;
                } else if (!st[i][j]) {
                    dfs(i, j, has_higher, has_lower);
                }
            }
}

int main() {

    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &h[i][j]);

    int peak = 0, valley = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j< n; j++)
            if (!st[i][j]) {
                int has_higher = false, has_lower = false;
                dfs(i, j, has_higher, has_lower);
                if (!has_higher) peak++;
                if (!has_lower) valley++;
            }

    printf("%d %d\n", peak, valley);

    return 0;
}