Cuidando la Granja.


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Rust, Scala, Swift, VB, Zig

La Granja tiene muchas colinas sobre las cuales el Granjero Juan desearía colocar guardias para asegurar la seguridad de sus valiosas vacas lecheras. El quiere saber cuántos guardias necesitará si él desea poner uno en la cumbre de cada colina. El tiene un mapa suministrado como una matriz de enteros; la matriz tiene N filas y M columnas. Cada miembro de la matriz es una altura H_{ij}. Ayúdelo a determinar el número de cumbres de colinas en el mapa.

Una cumbre de colina está compuesto por uno o mas elementos adyacentes de la matriz del mismo valor rodeados exclusivamente por el borde del mapa o por elementos con una altitud mas baja (menor). Dos elementos diferentes son adyacentes si la magnitud de diferencia en sus coordenadas X no es mayor que 1 y la magnitud de diferencias en sus coordenadas Y también no es mayor que 1.

Entrada

  • Línea 1: Dos enteros separados por espacio: N y M.
  • Líneas 2..N+1: La línea i+1 describe la fila i de la matriz con M enteros separados por espacios: H_{ij}.

Salida

Un solo entero que especifica el número de cumbres de colinas.

Restricciones

  • 1 < N \leq 700
  • 1 < M \leq 700
  • 0 \leq H_{ij} \leq 10,000

Ejemplo de Entrada

8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0

Ejemplo de Salida

3

Detalles de la Salida: Hay tres picos. Uno con altura 4 en la izquierda superior, uno de los puntos con altura 2 en la parte inferior, y uno de los puntos con altura 1 en la esquina superior derecha.


Comments

There are no comments at the moment.