Plages du pacifique – Regional event 2003

Level 4

ENONCE

On vous donne en paramètre un tableau d'entiers 2D, 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.

CONTRAINTES

  • 1 \<= L, H \<= 100, où L et H sont la largeur et la hauteur du tableau décrivant la zone..

ENTREE

  • 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 H lignes du tableau, sous la forme de L chiffres (0 ou 1), sans espaces.

SORTIE

Vous devez écrire une ligne sur la sortie :

  • Le nombre de plages de l'île.

Runtime constraints

Maximum memory usage
1000 kilobytes
Maximum execution time
250 milliseconds

Input/output samples

Submit your solution

You have to register or log in to be able to submit your solution.