Exploración Espacial.


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Las vacas del Granjero Juan han volado finalmente al espacio y ahora están flotando en el espacio en su Muunave. Las vacas quieren llegar en su travesía a la luna Io de Júpiter, pero para ello deben primero viajar a través del peligroso cinturón de asteroides.

Bessie está piloteando la nave a través de este peligroso sector N x N del espacio. Los asteroides en este sector abarcan algún número de cuadrados 1 x 1 de rocas espaciales conectados por sus lados (dos cuadrados compartiendo únicamente una esquina cuentan como dos asteroides distintos). Ayude a Bessie a maniobrar a través del campo contando el número de asteroides distintos en todo el sector.

Considere el espacio 10 x 10 mostrado a continuación en la izquierda. Los '*'s representan pedazos de asteroides, y cada '.' representan un espacio vacío. El diagrama en la derecha muestra una numeración arbitraria aplicada a los asteroides.

           ...**.....           ...11.....
           .*........           .2........
           ......*...           ......3...
           ...*..*...           ...3..3...
           ..*****...           ..33333...
           ...*......           ...3......
           ....***...           ....444...
           .*..***...           .5..444...
           .....*...*          ......4..6
           ..*.......          ..7.......

Es fácil ver que hay 7 asteroides en el sector.

Entrada

  • Línea 1: Un solo entero: N (1 \leq N \leq 1,000)
  • Líneas 2..N+1: La línea i+1 contiene la fila i del campo de asteroides: N caracteres

Salida

Un solo entero indicando el número de asteroides en el campo.

Ejemplo de Entrada

10
...**.....
.*........
......*...
...*..*...
..*****...
...*......
....***...
.*..***...
.....*...*
..*.......

Ejemplo de Salida

7

USACO JAN11 Bronze Problem: space


Comments

There are no comments at the moment.