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 cependant écrire un programme comptant pour lui le nombre d'îles présentes sur cette carte.

Entrée

  • Sur la première ligne, la hauteur de la carte
  • Sur la deuxième ligne, 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 case de terre, jointes par les côtés. Deux cases en diagonales ne sont pas jointes.

Sortie

  • Sur une ligne, suivie par un retour à la ligne, le nombre d'îles sur la carte.

Contraintes

  • x <= 1000
  • y <= 1000

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.