Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

TETRMG14 - Tetris Extreme

No jogo individual Tetris, uma sequência aleatória de tetrominós cai do topo de uma grade de M linhas e N colunas. Cada tetrominó ocupa quatro posições na grade e tem um dos formatos abaixo. Chamamos cada uma dessas posições ocupadas de

O objetivo do jogo é posicionar os tetrominós de modo a formar linhas horizontais de N unidades de largura na grade. Essas linhas desaparecem assim que são formadas, fazendo com que todos os blocos acima delas caiam. Para formá-las, é possível mover os tetrominós para os lados ou rotacioná-los 90 graus em qualquer direção durante a queda. Cada linha formada vale um ponto.

A figura abaixo mostra uma grade com um tetrominó que acaba de começar a cair.

Algumas variantes do jogo tetris incorporam funções especiais. Uma dessas funções é conhecida como gravidade. Quando a gravidade é acionada, todos os tetrominós e pedaços de tetrominós na grade são divididos em seus blocos constituintes. Esses blocos caem em direção à base da grade, o que pode levar a formação de novas linhas e fazer com que o jogador ganhe pontos. A figura abaixo mostra o que acontece se o jogador decidir usar a função gravidade na grade anterior. Primeiro os pedaços de tetrominós caem, formando duas linhas. Depois, essas linhas somem e os demais blocos caem, contabilizando dois pontos.

Saber usar a função gravidade é uma arte que poucos dominam. Em muitos casos, essa função leva a formação de grades com colunas em branco como ocorreu no exemplo, e isso acaba dificultando o jogo.

Nesse problema, você deve escrever um programa que compute o maior número de pontos que é possível fazer se o jogador posicionar o tetrominó que está caindo de forma ótima (levando em conta translação e rotação) e, em seguida, utilizar a função gravidade.

Entrada

Há vários casos de teste. Cada caso de teste começa com uma linha contendo três inteiros M, N e K.

M e N indicam o número de linhas e de colunas da grade, respectivamente (5 ≤ M ≤ 50 e 4 ≤ N ≤ 100000). $K indica qual é o próximo tetrominó a cair. A numeração dos tetrominós é mostrada na primeira figura.

Em seguida, há M linhas com N caracteres “.” ou “#” em cada uma. O caractere “.” é utilizado para indicar um espaço em branco. Já o caractere “#” indica uma posição preenchida por um bloco, que pode pertencer tanto a um tetrominó completo quanto a um pedaço de tetrominó. Os casos de teste não contêm linhas inteiramente preenchidas nem blocos nas quatro primeiras linhas.

A entrada termina com M=N=K=0.

Saída

Para cada caso de teste, imprima uma linha contendo um único número: a pontuação máxima que é possível conseguir se o jogador posicionar o o novo tetrominó na grade da melhor forma possível e, em seguida, acionar a função gravidade.

Exemplos

Entrada:
22 12 7
............
............
............
............
............
............
............
............
............
............
............
............
............
............
.....#......
.....#......
.....#......
.....#..###.
.....#######
###########.
####...####.
######.#####
7 12 6
............
............
............
............
.###########
.###########
..##########
0 0 0

Saída:
2
3

No segundo exemplo, é possível conseguir 3 pontos rotacionando a peça 90 graus no sentido horário e movendo-a até o canto esquerdo. Note que, em função da gravidade, não é necessário que a peça se encaixe completamente.


Adicionado por:Wanderley Guimarăes
Data:2014-07-10
Tempo limite:4s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Maratona Mineira 2014

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.