| Submeter | Todas submissőes | Melhores | Voltar |
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 |