AcWing 1106. 山峰和山谷    原题链接    中等

作者： 作者的头像   小呆呆 ,  2020-01-25 21:34:19 ,  所有人可见 ,  阅读 2613

11


1

算法分析

根据题目描述

  • 1、没有比它高的叫山峰

  • 2、没有比它矮的叫山谷

  • 3、还存在又比它高，又比它矮的不算山峰也不算山谷

步骤

  • 找到高度一致的连通块，若该连通块周围

    • 没有存在比它高的则该连通块叫山峰

    • 没有存在比它矮的则该连通块叫山谷

时间复杂度 $O(n^2)$

参考文献

算法提高课

Java 代码

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

public class Main {
    static int N = 1010;
    static int n;
    static boolean has_higher;
    static boolean has_lower;
    static int[][] g = new int[N][N];
    static boolean[][] st = new boolean[N][N];
    static void bfs(int x,int y)
    {
        Queue<PIIs> q = new LinkedList<PIIs>();
        q.add(new PIIs(x,y));
        st[x][y] = true;
        while(!q.isEmpty())
        {
            PIIs t = q.poll();
            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(st[i][j]) continue;*/
                    if(g[i][j] != g[t.x][t.y]) 
                    {
                        if(g[i][j] > g[t.x][t.y]) has_higher = true;
                        else has_lower = true;
                    }
                    else if(!st[i][j])
                    {
                        q.add(new PIIs(i,j));
                        st[i][j] = true;
                    }
                }
            }

        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(reader.readLine().trim());
        for(int i = 0;i < n;i ++)
        {
            String[] s1 = reader.readLine().split(" ");
            for(int j = 0;j < n;j ++)
            {
                g[i][j] = Integer.parseInt(s1[j]);
            }
        }
        int peak = 0, valley = 0;
        for(int i = 0;i < n;i ++)
        {
            for(int j = 0;j < n;j ++)
            {
                if(!st[i][j])
                {
                    has_higher = false;
                    has_lower = false;

                    bfs(i,j);
                    if(!has_higher) peak ++;
                    if(!has_lower) valley ++;

                }
            }
        }
        System.out.println(peak + " " + valley);
    }
}
class PIIs
{
    public int x;
    public int y;
    public PIIs(int x,int y)
    {
        this.x = x;
        this.y = y;
    }
}

10 评论

用户头像
skymiles   2022-08-08 22:56         踩      回复

if(st[i][j]) continue;
这句为啥注释掉?

用户头像
IF_3   2022-10-21 16:14      2    踩      回复

如果提前加了st[i][j] == true的话,不能与之前标记过的的山脉判断高度了

用户头像
最低甜度   7个月前    回复了 IF_3 的评论         踩      回复

你好，对你这句话似懂非懂，我有点象不太明白，可以详细说下嘛，为什么不在这里加入st[i][j] == true

用户头像
BLOODHOUND   2022-03-09 10:21         踩      回复

dfs为什么会超时呀

用户头像
目目目   2022-03-23 20:18         踩      回复 
#include<iostream>
#include<vector>

using namespace std;

typedef pair<int,int> PII;

const int N=1010;

int n;
int g[N][N];
bool st[N][N];
int dx[8]={-1,-1,-1,1,1,1,0,0},dy[8]={1,0,-1,1,0,-1,1,-1};
bool has_lower,has_higher;

void dfs(int x,int y)
{
    st[x][y]=true;

    for(int i=0;i<8;i++)
    {
        int nx=x+dx[i],ny=y+dy[i];

        if(nx>=1&&nx<=n&&ny>=1&&ny<=n)
        {
            if(!st[nx][ny]&&g[nx][ny]==g[x][y])
            {
                dfs(nx,ny);
            }
            if(g[nx][ny]<g[x][y]) has_lower=true;
            if(g[nx][ny]>g[x][y]) has_higher=true;
        }
    }
}

int main()
{
    cin>>n;

    for(int i=1;i<=n;i++) 
      for(int j=1;j<=n;j++)
        cin>>g[i][j];

    int peak=0,valley=0;

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

    cout<<peak<<' '<<valley; 

    return 0;
}
用户头像
目目目   2022-03-23 20:18         踩      回复

不超

用户头像
BLOODHOUND   2022-03-23 21:44    回复了 目目目 的评论         踩      回复

我感觉是语言的问题。。Java不知道为什么

用户头像
BLOODHOUND   2022-03-23 21:45    回复了 目目目 的评论         踩      回复 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.*;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    static int N = 1010, n;
    static int[][] g = new int[N][N],dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,1},{1,-1},{-1,-1}};
    static boolean[][] ju = new boolean[N][N];
    static PrintWriter w = new PrintWriter(System.out);
    static boolean up,down;
    static int l = 0, r = 0;
    public static void main(String[] args) {
        InputReader s = new InputReader();
        n = s.nextInt();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                g[i][j] = s.nextInt();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(!ju[i][j]){
                    up = false;down = false;
                    dfs(i,j);
                    if(!up)l++;
                    if(!down)r++;
                }
            }
        }
        w.write(l+" "+r);
        w.flush();
    }
    public static void dfs(int x,int y){
        ju[x][y]=true;
        for(int i=0;i<8;i++){
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            if(nx<0 || ny<0 || nx>=n || ny>=n)continue;
            if(g[x][y]!=g[nx][ny]){
                if(g[nx][ny]>=g[x][y])up = true;
                else if(g[nx][ny]<=g[x][y]) down = true;
            }else{
                if(!ju[nx][ny]){
                    dfs(nx,ny);
                }
            }
        }
    }
}
class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader() {
        reader = new BufferedReader(new InputStreamReader(System.in), 32768);
        tokenizer = null;
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }
}
用户头像
ddoubest   2022-12-10 21:52         踩      回复

暂时没有看到dfs能过这题的java代码，dfs会显示TLE。我个人分析是dfs会爆栈，例如n=1000并且每个格子的高度w都相同时，栈的层数会来到$10^6$级别，我个人电脑测试是爆栈的。但是y总告诉我，如果java爆栈是RE或者SF，我也挺疑惑的。

用户头像
BLOODHOUND   2022-12-12 20:33    回复了 ddoubest 的评论         踩      回复

java确实很容易爆栈。