题目描述

求两类连通块（山峰和山谷）的数量

思路

bfs求连通块

难点

怎么判断一个连通块是山峰还是山谷。
—>根据每个点的相邻点情况判断。相邻点就是每个点出队时，所能遍历到的所有点。就是在遍历其他点时判断。
----------

算法1

java代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static int N=1010;
    public static int n;
    public static int[][] g=new int[N][N];
    public static boolean[][] st=new boolean[N][N];
    public static Queue<Pair2> q=new LinkedList<>();
    public static int peak,valley;
    public static boolean has_high,has_low;
    public static int[] dx={-1,-1,0,1,1,1,0,-1};
    public static int[] dy={0,1,1,1,0,-1,-1,-1};
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        n=Integer.parseInt(s);
        for(int i=0;i<n;i++){
            String[] s1 = br.readLine().split(" ");
            for(int j=0;j<n;j++){
                g[i][j]=Integer.parseInt(s1[j]);
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(!st[i][j]){
                    has_high=false;has_low=false;
                    bfs(i,j);
                    if(!has_high){
                        peak++;
                    }
                    if(!has_low){
                        valley++;
                    }
                }
            }
        }
        System.out.println(peak+" "+valley);
    }
    public static void bfs(int sx,int sy){
        Pair2 p=new Pair2(sx,sy);
        q.add(p);
        st[sx][sy]=true;
        while(!q.isEmpty()){
            Pair2 t=q.poll();
            for(int i=0;i<8;i++){
                int x=t.x+dx[i];
                int y=t.y+dy[i];
                if(x<0||x>=n||y<0||y>=n){
                    continue;
                }
                if(g[x][y]!=g[t.x][t.y]){
                    if(g[x][y]>g[t.x][t.y]){
                        has_high=true;
                    }else {
                        has_low=true;
                    }
                    continue;
                }
                if(st[x][y]){
                    continue;
                }
                q.add(new Pair2(x,y));
                st[x][y]=true;
            }
        }
    }
}
class Pair2{
    int x;
    int y;
    public Pair2(int x,int y){
        this.x=x;
        this.y=y;
    }
}