Bessie mâchait des pousses tendres et, comme les vaches, réfléchissait à l’univers. Elle ne savoure que l’herbe des vastes pâturages au niveau de base de la ferme. À seulement 1 mètre plus haut, elle est plus dure et moins appétissante ; elle empire avec l’altitude.

Tout en mâchant, elle comprend que cette herbe pousse sur les flancs des collines, formant des « îles » au milieu d’une mer d’herbe tendre, verdoyante, délicieuse et abondante.

Bessie enfile sa blouse de laboratoire et décide de compter ces îles. Elle dessine une carte de $R$ rangées ($1 \lt R \le 1,000$) et $C$ colonnes ($1 \lt C \le 1,000$) de carrés de $1 \times 1$ mètre. Elle mesure l’altitude au-dessus du niveau de base et l’arrondit en entier non négatif. Elle remarque avec faim que l’herbe savoureuse a toujours l’altitude 0.

Elle compte les îles. Deux carrés voisins horizontalement, verticalement ou en diagonale appartiennent à la même île.

Combien d’îles de mauvaise herbe compte-t-elle pour chaque carte donnée ?

Entrée

• Ligne $1$ : deux entiers séparés par un espace : $R$ et $C$.

• Lignes $2,\ldots,R+1$ : la ligne $i+1$ décrit la rangée $i$ avec $C$ entiers séparés par des espaces.

Sortie

• Ligne $1$ : un entier, le nombre d’îles.

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

2

Remarque

Il y a deux îles : la grande à gauche rejoint le bas par une diagonale, et la petite est dans le coin supérieur droit.

Auteur du problème : Fatih, 2008