Certamente já ouviste
falar no "matematicamente famoso" Triângulo de Pascal, um triângulo
numérico infinito formado pelos coeficientes binomiais, cujo nome se
deve ao facto de ser sido extensivamente estudado pelo matemático
francês Blaise Pascal, aquele cujo nome foi usado para batizar a
linguagem de programação Pascal. Pois bem este problema é precisamente
sobre triângulos de Pascal, mas de um tipo bem diferente!
Nas Olimpíadas Internacionais de Informática é costume a prova decorrer numa sala única (geralmente um pavilhão muito amplo) que alberga todos os concorrentes. Estes estão distribuídos com posições bem definidas, de acordo com uma grelha. Sendo tu um membro do comité científico, tens acesso às linguagens de programação que cada concorrente está a usar, entre as quais a linguagem Pascal. Como és entusiasta da Matemática, não pudeste deixar de reparar que na sala da prova, vista de cima, existe um bem desenhado triângulo de alunos que estão a programar... em Pascal! Verdadeiramente entusiasmado, decides procurar o maior "triângulo de Pascal" na sala, ou seja, o maior triângulo formado por alunos que estão a programar em Pascal.
Podes pensar na sala de prova como uma grelha cartesiana, onde cada célula representa um concorrente. Uma célula contém a letra 'P' se for um aluno que está a usar Pascal, e 'C' se for um aluno que está a usar C ou C++. Para nós, hoje, um triângulo de Pascal é um conjunto de células com 'P' que formam um triângulo tal como é exemplificado na figura seguinte, com quatro triângulos de tamanhos diferentes:
Os triângulos podem não estar nesta direção (todos estes têm a base horizontal e o vértice oposto para cima), mas têm de ter sempre um dos seus lados paralelos ao eixo dos X, ou ao eixo dos Y. Isto faz com que existam quatro orientações possíveis, como exemplificado na figura seguinte para triângulos com tamanho 3:
Para um sala de prova cheia, queremos calcular qual o tamanho do maior triângulo formado exclusivamente por concorrentes que estão a usar Pascal. Por exemplo, para a grelha seguinte, o maior triângulo de Pascal tem tamanho 4:
Para um caso geral, consegues calcular o tamanho do maior triângulo de Pascal?
Dada uma grelha de concorrentes com L linhas e C colunas, com cada célula da grelha indicando se o concorrente dessa posição está ou não a usar Pascal, a tua tarefa é descobrir qual o tamanho do maior triângulo de Pascal possível, ou seja, formado unicamente por concorrentes que estão a usar Pascal. Deve considerar-se as quatro orientações possíveis para os triângulos.
Na primeira linha do input vêm dois números inteiros L e C, separados por um espaço, indicando respetivamente o número de linhas e de colunas da grelha de concorrentes.
Seguem-se exatamente L linhas, cada um com C letras, indicando a linguagem utilizada pelos concorrentes de cada posição. 'P' é usado para os concorrentes que estão a usar Pascal, e 'C' para os que estão a usar C ou C++.
O output deve ser constituído por uma única linha contendo um número inteiro indicando o tamanho do maior triângulo de Pascal da sala de prova, tal como foi atrás descrito. Se todos os concorrentes estiverem em C ou C++, o maior triângulo terá tamanho zero.
São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:
| 1 ≤ L, C ≤ 1500 | Dimensões da grelha de concorrentes |
Para um conjunto de casos de teste valendo 40% dos pontos, acontece sempre que L e C são menores ou iguais a 25.
8 10 PCPCCPCCPC CPPPPCPPPP PCPPPPPPPC CPCPPPPPPC CPCCPPPCPC CCPCCPCPCP CPCPPPCCPC PPPPCCPCCC
4