Nos dias de hoje é comum o acesso a uma ferramenta de mapas online sempre que desejamos planear uma viagem ou simplesmente visitar "virtualmente" um determinado sítio. Certos da massificação dessa utilização, os responsáveis pelo marketing não perderam a oportunidade de a rentabilizar. Como uma das vistas mais comuns é a de satélite, com imagens vistas completamente por cima, arranjaram maneira de criar uma publicidade que sobressai precisamente quando estamos a visualizar o mapa online.
Tu trabalhas para a SONI (SOluções Nacionais Inteligentes), uma enorme empresa tecnológica cujo logotipo principal assenta na figura geométrica de um losango. É sabido que o maior fornecedor de imagens de satélite vai amanhã actualizar as imagens da região, tirando novas fotografias de satélite. De acordo com o plano, a SONI quer criar um enorme logotipo no chão, num terreno inutilizado que possui. O problema é que o terreno está cheio de frondosas árvores, algumas das quais de espécies protegidas, que se fossem cortadas fariam levantar um coro de protestos dos ecologistas, da população local e das autoridades. Sendo assim, é preciso descobrir qual o maior losango que se pode criar sem deitar abaixo nenhuma árvore. Fazer isso à mão é muito demorado e pouco rigoroso e por isso a SONI veio encomendar-te o serviço!
O mapa do terreno é dado como um quadriculado de C colunas por L linhas, onde '.' representa uma quadrícula vazia e 'A' representa uma árvore. Um exemplo de um mapa de 9 colunas por 6 linhas (com as colunas e linhas numeradas começando do topo esquerdo) seria:
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
1 | A | . | . | . | A | . | . | A | . |
2 | . | . | . | A | . | . | . | . | . |
3 | . | . | . | . | A | . | . | . | A |
4 | . | . | . | . | . | . | . | . | . |
5 | . | . | . | . | A | . | . | . | . |
6 | A | . | . | . | . | A | . | . | A |
O losango que se quer desenhar é uma figura geométrica com quatro lados de igual comprimento, com os lados a serem paralelos dois a dois. A empresa apenas quer losangos "perfeitos" que podem ser vistos na figura seguinte, detalhando um losango de tamanho 1, um de tamanho 2, outro de tamanho de 3 e finalmente um de tamanho 4. O "tamanho" do losango é representando pela medida do lado:
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | # | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | # | . | . | . | . | . | . | # | # | # | . | . | . |
. | . | . | . | . | # | . | . | . | . | # | # | # | . | . | . | . | # | # | # | # | # | . | . |
. | # | . | . | # | # | # | . | . | # | # | # | # | # | . | . | # | # | # | # | # | # | # | . |
. | . | . | . | . | # | . | . | . | . | # | # | # | . | . | . | . | # | # | # | # | # | . | . |
. | . | . | . | . | . | . | . | . | . | . | # | . | . | . | . | . | . | # | # | # | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | # | . | . | . | . |
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
Para o mapa indicado anteriormente, o maior losango que se pode criar sem deitar abaixo nenhum árvore tem tamanho 3 e está indicado na figura seguinte, com o seu ponto superior na intersecção da 3ª coluna com a 2ª linha:
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
1 | A | . | . | . | A | . | . | A | . |
2 | . | . | # | A | . | . | . | . | . |
3 | . | # | # | # | A | . | . | . | A |
4 | # | # | # | # | # | . | . | . | . |
5 | . | # | # | # | A | . | . | . | . |
6 | A | . | # | . | . | A | . | . | A |
Nota que para um caso geral, o tamanho máximo do losango é apenas limitado pelo mapa. Caso existam vários losangos de tamanho máximo possível, a SONI decidiu que deves escolher aquele cujo ponto superior esteja o mais acima possível, ou seja, com o menor número de linha possível. Caso subsista um empate, deves escolher o losango que esteja o mais à esquerda possível, ou seja, com o menor número de coluna possível. Por exemplo, no mapa dado, um losango de tamanho 3 podia também ser criado com o ponto superior na intersecção da 7ª coluna com a 2ª linha. No entanto, pelas regras de desempate, preferimos o losango anteriormente indicado, que está nas mesmas linhas, mas mais à esquerda.
Dado um mapa com C colunas e L linhas e a localização de um conjunto de árvores nos limites desse mapa, a tua tarefa é descobrir qual o maior losango que é possível criar nesse mesmo mapa que não toque em nenhuma das árvores. Caso existam vários losangos de tamanho máximo, deves escolher aquele que estiver o mais acima possível e em caso de novo empate deves escolher o que estiver mais à esquerda.
Na primeira linha do input vêm dois números inteiros C e L, separados por um espaço, indicando o número de colunas e o número de linhas do mapa, respectivamente.
Seguem-se exactamente L linhas, cada uma contendo exactamente C caracteres, descrevendo o mapa. Cada um dos caracteres pode ser:
É garantido que em todos os testes haverá pelo menos uma quadrícula sem árvore.
O output deve ser constituído exactamente por duas linhas. A primeira deve conter um único número inteiro indicando o tamanho do maior losango que é possível de criar no mapa. A segunda linha deve conter dois números inteiros, separados por um espaço, indicando respectivamente a coluna e a linha do ponto superior do losango a criar.
Se existirem vários losangos possíveis de tamanho máximo, deves escolher aquele estiver o mais acima possível (menor número de linha) e em caso de novo empate aquele que estiver o mais à esquerda (menor número de coluna).
São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:
1 ≤ L,C ≤ 1 000 | Dimensões do mapa |
Para um conjunto de casos de teste valendo 50% dos pontos, o número de linhas e de colunas é inferior ou igual a 25.
9 6 A...A..A. ...A..... ....A...A ......... ....A.... A....A..A
3 3 2