Cuidando la Granja.


Submit solution

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

Author:
Problem type

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 (1 < N \leq 700) filas y M (1 < M \leq 700) columnas. Cada miembro de la matriz es una altura H_{ij} ( 0 \leq H_{ij} \leq 10,000). 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

  • Línea 1: Un solo entero que especifica el número de cumbres de colinas.

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.