Problema C - O Algodão Não Engana

O local onde se vai realizar a próxima edição das Olimpíadas Nacionais de Informática é uma sala grande coberta de azulejos que formam uma grelha de D por D. Os azulejos são todos iguais, mas alguns estão sujos e outros estão limpos.

Para representar o estado da sala usamos uma grelha de D por D caracteres onde um . representa um azulejo limpo e um # um azulejo sujo. Por exemplo, podemos considerar a seguinte grelha com D = 4:

Que seria representada da seguinte forma:

....
####
..#.
#.#.

Onde a primeira fila é composta de azulejos limpos, a segunda de azulejos sujos, a terceira tem um azulejo sujo na terceira coluna e a última fila tem um azulejo sujo na primeira e terceira colunas.

Parte I

Queremos colocar uma estação de servidores para suportar a prova, mas só a podemos colocar em azulejos limpos. A estação de servidores é uma linha e por isso terá de ser colocada num segmento horizontal ou vertical de azulejos limpos. Para ajudar a determinar a sua melhor posição, a tua tarefa é determinar o comprimento do maior segmento vertical ou horizontal de azulejos limpos.

Exemplo

Se D = 4 tivermos o seguinte estado de azulejos:

Então podemos usar os três primeiros azulejos da última coluna, ou seja a resposta é 3. A figura seguinte ilustra esta solução:

Restrições:

São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:

Os casos de teste desta parte do problema estão organizados em dois grupos:

Parte II

A zona de concorrentes terá a forma de um quadrado e, assim como na Parte I, só pode ser colocada em azulejos limpos. Para ajudar a determinar a sua melhor posição, a tua tarefa é determinar a área do maior quadrado de azulejos limpos.

Exemplo

Se D = 4 tivermos o seguinte estado de azulejos:

Então podemos formar um quadrado de lado 2 e de área 4. A figura seguinte ilustra esta solução:

Restrições:

São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:

Os casos de teste desta parte do problema estão organizados em três grupos:

Sumário de subtarefas

Os casos de teste do problema estão organizados em 5 grupos com restrições adicionais diferentes:

Input

A primeira linha contém um inteiro P, que representa a parte que o caso de teste representa. Se for 1, então o caso de teste refere-se à Parte I, se for 2 então refere-se à Parte II.

Segue-se uma linha com um inteiro D, representando a dimensão da grelha.

Seguem-se D linhas com D caractéres cada (que serão ou . ou #), representando o estado dos azulejos.

Output

Parte I

O output deve conter uma linha com o comprimento do maior segmento.

Parte II

O output deve conter uma linha com a área do maior quadrado.

Input do Exemplo 1

1
4
##..
..#.
..#.
##.#

Output do Exemplo 1

3

Explicação do Exemplo 1

Este exemplo corresponde ao exemplo mencionado no enunciado da Parte I.

Input do Exemplo 2

2
4
##..
..#.
..#.
##.#

Output do Exemplo 2

4

Explicação do Exemplo 2

Este exemplo corresponde ao exemplo mencionado no enunciado da Parte II.