$$\color{Red}{山峰和山谷——Flood Fill}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

输入格式

第一行包含一个正整数 n，表示地图的大小。

接下来一个 n×n 的矩阵，表示地图上每个格子的高度 w。

输出格式

共一行，包含两个整数，表示山峰和山谷的数量。

数据范围

1 ≤ n ≤ 1000

0 ≤ w ≤ 10 ^ 9

输入样例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

输出样例1：

2 1

样例解释1

输入样例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

输出样例2：

3 3

样例解释2

思路

思路仍然是Flood Fill 的模板，但是这道题不同的是，我们有一个如果平面高度均相同就既是山谷也是山峰的条件。
同时如果既有比它高的联通块，又有比它低的连通块，就什么也不算。

综合考虑我们就不能在if 条件下靠成立进行自增，而是在不满足的情况下自增，且不需要else if进行分支。

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 1010, n, peek, valley;
    static boolean[][] st = new boolean[N][N];
    static int[][] h = new int[N][N];
    static PII[] q = new PII[N * N];
    static boolean has_higher, has_lower;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static class PII {
        int x, y;

        public PII(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

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

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            String[] s = br.readLine().split(" ");
            for (int j = 0; j < n; j++) h[i][j] = Integer.parseInt(s[j]);
        }
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (!st[i][j]) {
                    bfs(i, j);
                    if (!has_higher) peek++;
                    if (!has_lower) valley++;
                    has_higher = false;
                    has_lower = false;
                }
        System.out.println(peek + " " + valley);
    }
}