Costa
Por OBI - Olimpíada Brasileira de Informática 2012 
Brazil
Por OBI - Olimpíada Brasileira de Informática 2012 Brazil
A Nlogônia é um país tropical, com muitas belezas naturais internacionalmente famosas; dentre elas, encontram-se as belas praias que compõem o arquipélago do país, que todo verão recebem milhões de turistas estrangeiros.
O Ministério do Turismo da Nlogônia está preparando o país para a chegada dos turistas, mas para fazer seu planejamento, precisa saber a extensão da costa nlogônica. Para isso, ele gerou um mapa que divide o território nacional em vários quadrados, que podem ser ocupados por água ou por terra; considera-se que um quadrado é parte da costa nlogônica se ele é um quadrado ocupado por terra que tem um lado em comum com um quadrado ocupado por água.
Na figura abaixo, (a) mostra um trecho do mapa gerado e (b) mostra os quadrados do trecho dado que são costa.
Como a Nlogônia é um país muito grande, o ministro do turismo pediu que você escrevesse um programa que, dado o mapa da Nlogônia, determina a extensão da costa nlogônica.
A primeira linha da entrada contém dois inteiros M e N (1 ≤ M, N ≤ 1000) indicando, respectivamente, o número de linhas e o número de colunas do mapa. Cada uma das M linhas seguintes contém N caracteres: um caractere ‘.’ indica que aquele quadrado do território é ocupada por água; um caractere ‘#’ indica que aquele quadrado do território é ocupada por terra.
Considere que todo o espaço fora da área do mapa é ocupado por água.
Seu programa deve imprimir uma única linha contendo um único inteiro, indicando quantos quadrados do território fazem parte da costa da Nlogônia.
| Exemplos de Entrada | Exemplos de Saída |
|
5 5 ..... ..#.. .###. ..#.. ..... |
4 |
|
10 10 .......... .....###.. ....#####. .#...##... .......... .......##. .##....... ..##...... ..###..... ..#####... |
22 |