Plages du Pacifique – Regional event 2003

Level 4

É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$

Runtime constraints

Maximum memory usage
1000 kilobytes
Maximum execution time
250 milliseconds

Input/output samples

Sample input
5 5
00000
01110
01110
01110
00000
Sample output
8
Sample input
5 5
00000
01110
01010
01110
00000
Sample output
8
Sample input
6 6
000000
011110
011110
011010
011100
000000
Sample output
13
Note

Notez ici qu'il n'y a pas de lac, la case d'eau entouré de terre appartient à la mer (voyez ça comme une crique).

Submit your solution

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