AcWing 1106. 山峰和山谷
原题链接
中等
作者:
栗子ing
,
2022-05-14 17:19:26
,
所有人可见
,
阅读 271
import java.util.*;
public class Main{
static int N = 1010,n,hh,tt;
static int[][] g = new int[N][N];
static boolean[][] st = new boolean[N][N];
static boolean has_higher;//如果旁边的是比我矮的,那我被标记说明是山峰
static boolean has_lower;//如果旁边的是比我高的,那我被标记说明是山谷
static PII[] q = new PII[N * N];
public static void bfs(int x,int y){
hh = 0;tt = -1;
q[++ tt] = 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(i == t.x && j == t.y ) continue;
if(i < 0 || j < 0 || i >= n || j >= n) 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; // 剩下就是比我矮的1,那我就是山峰,将山谷标记
}else if(!st[i][j]){ // 剩下的情况就是等于,就是可以练成一片的山峰或者山谷,进行bfs
st[i][j] = true;//标记已经来过了
q[++ tt] = new PII(i,j);//然后存入队列中
}
}
}
}
}
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
for (int i = 0 ; i < n ; i ++ ){
for (int j = 0 ; j < n ; j ++ ){
g[i][j] = scan.nextInt();
}
}
int peak = 0;
int 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 ++;//如果没有标记高的,那我就是山峰,山峰加1
if(!has_lower) valley ++;//如果没有标记矮的,那我就是山谷,山谷加1
}
}
}
System.out.print(peak + " " + valley);
}
}
class PII{
int x,y;
public PII(int x,int y){
this.x = x;
this.y = y;
}
}