Plages du Pacifique – Regional event 2003

Énoncé¶

On vous donne en paramètre un tableau d'entiers à deux dimensions, contenant uniquement des 0 ou des 1. Les 0 correspondent à des zones remplies d'eau, et les 1 correspondent à des zones remplies de terre. Ce tableau contient une île unique, c'est-à-dire une zone de 1 entourée de 0. On peut aller de toute case de cette île à n'importe quelle autre en se déplaçant uniquement sur des cases de terre, et en ne passant d'une case à l'autre que si les deux cases sont adjacentes (ont un côté commun).

Vous devez écrire une fonction qui calcule le nombre de plages de cette île, c'est-à dire le nombre de cases de terre, qui touchent une case de l'océan. Par toucher, on entend être adjacent (avoir un côté commun).

A l'intérieur de l'île peuvent se trouver des lacs, c'est-à-dire des zones d'eau entièrement entourées de terre : on peut en faire le tour en ne se déplaçant que sur des cases de terre. Une case de terre qui se trouve au bord du lac, mais ne touche pas l'océan ne doit pas être considérée comme une plage.

Attention, une case d'eau qui touche une case d'océan en diagonale, est également considérée comme une case d'océan, et non un lac : il est impossible d'en faire le tour en ne se déplaçant qu'horizontalement et verticalement.

L'île est toujours entièrement entourée d'eau. Les cases sur le bord du tableau sont donc toutes des cases d'eau, qui font partie de l'océan.

Entrée¶

• La première ligne de l'entrée contient deux nombres $L$ et $H$ : la largeur et la hauteur du tableau décrivant la zone où se trouve l'île.
• Les $H$ lignes suivantes décrivent les lignes du tableau, sous la forme de $L$ chiffres (0 ou 1), sans espace.

Sortie¶

Vous devez écrire une ligne sur la sortie :

• Le nombre de plages de l'île.

Contraintes¶

• $1 \le L, H \le 100$