LOST – Regional event 2013

Level 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

Runtime constraints

Maximum memory usage
100 kilobytes
Maximum execution time
200 milliseconds

Input/output samples

Sample input
3 3
~~~
~X~
~~~
Sample output
1
Sample input
10 10
~~~~~~~~~~
~XXX~~~~~~
~XXXX~~~~~
~~X~~~~~~~
~~~~~~~~~~
~~~~~~~~~~
~~~~XXX~~~
~~~~~XXX~~
~~~~~XX~~~
~~~~~~~~~~
Sample output
2
Sample input
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~~~~
~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~
Sample output
2
Sample input
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~~
Sample output
7

Submit your solution

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