Descrição
O planeta de Skyrk nunca vai conhecer a paz enquanto o malvado Mago estiver livre. Dessa vez, o malicioso plano do Mago foi armar uma bomba no meio da maior cidade do planeta. Mago aprecia observar o caos, então, ao invés de explodir a bomba imediatamente, ele colocou um temporizador na bomba e a deixou junto com um desafio. A bomba tem um teclado, e a solução do desafio desarma a bomba.
O desafio se chama Ominobox; ele consiste de uma caixa retangular com alguns cubos unitários dentro e de uma coleção de todos os possíveis N -ominos. Skyrk deve soltar todo omino em algum lugar da caixa para ganhar pontos. A pontuação máxima é a solução do Ominobox.
Um N -omino é uma coleção de N quadrados unitários arranjados com lados coincidentes. Um 1-omino é um quadrado unitário, e um N -omino é um (N − 1)-omino com pelo menos um dos seus lados ligados a um quadrado unitário.
A caixa tem uma superfície retangular e paredes verticais; cada um dos quadrados de um sistema Cartesiano de coordenadas em grade colocado na superfície da caixa possui uma pilha não negativa de cubos unitários. Os cubos não podem ser movidos.
Skyrk irá alinhar cada omino com os quadrados da grade, e soltá-lo na caixa. O omino irá cair até tocar um cubo ou o fundo. Não é permitido que Skyrk reflita ou rotacione o omino, e ele deve situar-se completamente dentro dos limites da caixa. O número de pontos obtidos após soltá-lo é a distância entre o omino e o topo da caixa. Após soltá-lo, Skyrk anota o número de pontos, remove o omino, e solta o próximo. A pontuação final é a soma de todos os pontos.
O tempo está passando e a contagem regressiva na bomba diz 5:00 (cinco horas!). Você consegue descobrir a pontuação máxima que Skyrk pode obter para desarmar a bomba e salvar o destino do planeta das mãos do vil Mago?
OBS:
No primeiro desafio, Fig. 1 mostra a melhor maneira de colocar o único 1-omino. O omino atinge o fundo da caixa na posição (1,0) e possui distância de 3 até o topo da caixa. Esta configuração rende um total de 3 pontos.
No segundo desafio, Fig. 2 e Fig. 3 mostram as melhores maneiras de colocar os dois 2-ominos. Na Fig. 2 o omino atinge a pilha de cubos de altura 1 na posição (0,0) e possui distância de 2 até o topo de caixa. Na Fig. 3 o omino atinge a pilha de cubos de altura 2 na posição (0,1) e possui uma distância de 1 até o topo de caixa. Esta configuração rende um total de 3 pontos.
No terceiro desafio, Fig. 4 mostra a melhor maneira de colocar o único 3-omino que cabe dentro da caixa. Esta configuração rende um total de 1 ponto.
No quarto desafio, Fig. 5-8 mostram as melhores maneiras de colocar os quatro 4-ominos que cabem dentro da caixa. Esta configuração rende um total de 5 pontos.
Entrada
A primeira linha contém T (T ≤ 200) — o número de desafios, após essa linha haverá T desafios.Cada desafio começa com uma linha com quatro inteiros R, C, H e N (1 ≤ R, C, H ≤ 30; 1 ≤ N ≤ 10) — as dimensões da superfície da caixa são R × C, a altura é H, e a ordem dos ominos é N . Cada uma das próximas R linhas contém C inteiros Hi,j (0 ≤ Hi,j ≤ H) — o número de cubos no quadrado (i, j) da grade.
Saída
Para cada desafio, imprima uma linha contendo X, onde X é a solução do Ominobox.
| Exemplos de Entrada | Exemplos de Saída |
|---|---|
|
4 |
3 |
Efetue Login ou Cadastre-se para submeter uma solução.
Criado por Davi Duarte Pinheiro | Adaptado por Erich Rodrigues | Competição: SBC - ACM/ICPC - Maratona de Programação de 2015