LOST – Épreuve régionale 2013

Niveau 4

Énoncé

Joseph marchand est perdu sur une île déserte. Il possède cependant une carte des environs. Il désire écrire un programme comptant pour lui le nombre d'îles présentes sur cette carte.

Entrée

  • Sur la première ligne, deux entiers séparés par une espace : la hauteur et la largeur de la carte
  • Sur les lignes suivantes, la carte. Un '~' représente de l'eau, un 'X' représente de la terre. Une île est définie comme étant un ensemble de cases de terre, jointes par les côtés. Deux cases en diagonales ne sont pas jointes.

Sortie

  • Le nombre d'îles sur la carte.

Contraintes

  • x <= 1 000
  • y <= 1 000

Contraintes d'exécution

Utilisation mémoire maximum
100 kilo-octets
Temps d'exécution maximum
200 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
3 3
~~~
~X~
~~~
Exemple de sortie
1
Exemple d'entrée
10 10
~~~~~~~~~~
~XXX~~~~~~
~XXXX~~~~~
~~X~~~~~~~
~~~~~~~~~~
~~~~~~~~~~
~~~~XXX~~~
~~~~~XXX~~
~~~~~XX~~~
~~~~~~~~~~
Exemple de sortie
2
Exemple d'entrée
20 20
~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~
~~~XXXXXXXXXXXXX~~~~
~~~XX~~~~~~~~XXX~~~~
~~~XX~XXXXXX~XXX~~~~
~~~XX~XXXXXX~XXX~~~~
~~~XX~XXXXXX~XXX~~~~
~~~XX~XXXXXX~XXX~~~~
~~~XX~XXXXXX~XXX~~~~
~~~XX~XXXXXX~XXX~~~~
~~~XX~XXXXXX~XXX~~~~
~~~XX~XXXXXX~XXX~~~~
~~~XX~XXXXXX~XXX~~~~
~~~XX~XXXXXX~XXX~~~~
~~~XX~~~~~~~~XXX~~~~
~~~XXXXXXXXXXXXX~~~~
~~~XXXXXXXXXXXXX~~~~
~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~
Exemple de sortie
2
Exemple d'entrée
20 10
~~~~~~~~~~
~X~~~~~~~~
~~~~~~~~~~
~~~~~~~~~~
~X~~~~X~~~
~~~~XXXXX~
~~~XX~~~Xx
~X~XX~X~XX
~~~XX~~~XX
~~~~XXXXX~
~~~~~~XX~~
~~~X~~~~~~
~~~XX~~~~~
~~XXXX~~~~
~~~XXX~~~~
~~~~X~~~~~
~~~~~~~X~~
~~~~~~~XXX
~~~~~~XXXX
~~~~~~XX~~
Exemple de sortie
7