La ferme a beaucoup de collines où Farmer John veut placer des gardes pour protéger ses précieuses vaches laitières.
Il se demande combien il en faut pour en mettre un à chaque sommet. Sa carte est une matrice d'entiers à $N$ lignes $(1 \lt N \le 700)$ et $M$ colonnes $(1 \lt M \le 700)$. Chaque élément est une altitude $H_{ij}$ $(0 \le H_{ij} \le 10,000)$. Aidez-le à compter les sommets.
Un sommet comprend un ou plusieurs éléments voisins de même valeur, entourés uniquement du bord de la carte ou d'éléments strictement plus bas. Deux éléments distincts sont voisins si la différence absolue de leurs coordonnées $X$ est au plus 1, et celle de leurs coordonnées $Y$ aussi.
Entrée
- Ligne 1 : deux entiers séparés par un espace, $N$ et $M$.
- Lignes $2,\ldots,N+1$ : la ligne $i+1$ décrit la ligne $i$ par $M$ entiers $H_{ij}$ séparés par des espaces.
Sortie
- Ligne 1 : un entier donnant le nombre de sommets.
Exemples
Entrée 1
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
Sortie 1
3
Remarque
Il y a trois sommets : le point de hauteur 4 en haut à gauche, un des points de hauteur 2 en bas, et un des points de hauteur 1 au coin supérieur droit.
Auteur du problème : Fatih Gelgi, 2008