2853 - Invenções de Bibika

  • ID: 2853
  • IdBecrowd: 2853
  • Tags: ad-hoc, estruturas-dados, geometria, grafos, strings
  • Nível: 7
  • Tempo Limite: 1 segundos
  • Memória: 200 MB
  • Categoria: Ad-Hoc
  • Autor: Dâmi Henrique, Inatel

Descrição

Bibika, uma mineira bacana, foi expulsa do Brasil por estar encomodando os políticos brasileiros com suas invenções mirabolantes. Sua última invenção foi o VDH (Vírus da Honestidade) que, quando em contato com um humano, o faria ser uma pessoa honesta para sempre (funcionaria até com os políticos!).

Após alguns meses vagando de país em país, ela conseguiu um lar fixo na China. Em um belo dia, quando estava tirando fotos na Muralha da China, teve uma ideia de como espalhar o VDH no Brasil. Sua ideia seria espalhar alguns robôs invisíveis (sim, ela inventou robôs invisíveis) pelas cidades do Brasil e esses robôs lançariam o VDH aos poucos (assim não chamaria tanta atenção) até que todo o Brasil fosse infectado.

Veremos o Brasil como um grid  N x M , onde em alguma(s) célula(s) desse grid existirá um robô equipado com o VDH.

Um robô consegue lançar o vírus para as quatro direções (Norte, Sul, Leste e Oeste) e inicialmente possui uma potência de lançamento igual a 1. Isso significa que no primeiro dia ele conseguirá infectar 1 célula em cada uma das direções. A cada novo dia sua potência aumenta em uma unidade, fazendo com que o robô no terceiro dia, por exemplo, infecte até 12 células, 3 em cada uma das direções.

Segue um exemplo das posições infectadas por um robô, representado pelo caracter @, em um total de quatro dias:

UOJ_383_G

UOJ_383_G

Mesmo inventando o vírus da honestidade e os robôs invisíveis, Bibika não sabe quantos dias serão necessários para infectar todo o território Brasileiro, dada uma configuração de robôs. Vale ressaltar que as células que possuem robôs já estão automaticamente infectadas.

Sua tarefa é ajudá-la nessa missão ou dizer que não é possível infectar todo Brasil dada a configuração de robôs de Bibika.

Entrada

A primeira linha contém dois inteiros N e M (1 ≤ N , M ≤ 1000), representando o tamanho do mapa do Brasil.

                Cada uma das próximas

N linhas conterão M caracteres ‘#’ ou ‘@’, onde ‘#’ representa uma área qualquer do território brasileiro e ‘@’ representa uma área com um robô invisível de Bibika.

Saída

Exiba um único inteiro, a quantidade de dias que serão necesários para infectar todo o Brasil. Caso seja impossível, imprima -1.

Exemplos

Exemplo de Entrada

5 6

                                #@##@#

                                #####@

                                ##@###

                                ###@##

                                @#####

Exemplo de Saída

4
Back to top