uCoder | 1181 | Nível: 4 | Tempo Limite: 5
Number Crush Saga
Adaptado por erich.rodriguesf
Competição: Interfatecs 2015
A Capivara Apps, uma das novas startups que estão surgindo no Centro-Oeste brasileiro, está desenvolvendo um jogo similar a um dos jogos mais viciantes lançados recentemente. O novo jogo se chama Number Crush Saga. É um jogo relativamente simples: para cada fase do jogo o jogador deve tentar agrupar peças do mesmo tipo para fazer o maior número de pontos possíveis.
A tabela a seguir indica o número de pontos para cada uma das combinações de peças possíveis.
A combinação de peças pode ser realizada tanto na horizontal como na vertical. O número de peças combinadas deve estar de acordo com a tabela 1 apresentada.
Quando um conjunto de peças do mesmo tipo é agrupado, as peças combinadas são retiradas do tabuleiro. Com isso, as peças que estão acima das peças removidas são deslocadas para posições inferiores no tabuleiro podendo gerar novas combinações e assim consecutivamente. As posições da parte superior do tabuleiro, nas colunas onde peças foram deslocadas para baixo, ficam vazias. No jogo não existe a entrada de novas peças no tabuleiro. As pontuações de todas as combinações geradas a partir de uma movimentação devem ser somadas para alcançar a pontuação final da jogada.
No total existem 5 tipos diferentes de peças correspondendo aos números de 1, 2, 3, 4 e 5. Desta forma, ao combinar pelo menos 3 peças com o mesmo número de forma sequencial (tanto na horizontal quanto na vertical) o jogador recebe 60 pontos, caso a remoção destas 3 peças não gere novas combinações. Movimentações que geram mais de uma combinação ao mesmo tempo, tanto na vertical quanto na horizontal, são somadas separadamente.
A movimentação das peças se dá através da troca entre duas peças vizinhas, comparando somente a peça acima, abaixo, à esquerda e à direita (não é possível trocar uma peça com a sua diagonal). Neste jogo é possível movimentar as peças sem que seja obrigatória uma combinação mínima entre as peças vizinhas. Se isso acontecer, a pontuação para a jogada é 0 (zero).
A Tabela 2 apresenta uma matriz com 5 linhas e 5 colunas que representa um tabuleiro completo de jogo, com peças numeradas distribuídas por toda a matriz.
Ao mover a peça 4x3 (linha 4 e coluna 3) para a posição 4x4 uma única combinação vai ser gerada com 3 números 3 na coluna 4. Com esta jogada, o jogador obtém 60 pontos no total. As peças nas posições 0x4 e 1x5 vão ser movimentadas para baixo e ficaram nas posições 4x4 e 3x4, respectivamente. Depois da movimentação as posições 0x4 e 1x5 ficaram vazias, como apresentado na Tabela 3.
No exemplo da Tabela 4, caso o jogador mova a peça na posição 3x1 para a posição 3x2, a peça de número 1 é trocada pela peça de número 2. Com essa jogada, o jogador obtém três combinações: a combinação de 3 números 1 na coluna 1; 3 números 2 na coluna 2; e a combinação de 3 peças com o número 3 na linha 2 depois da remoção das seis peças anteriormente combinadas (3 números 1s e 3 números 2s). Após a execução da movimentação o tabuleiro resultante é apresentado na Tabela 5, Com essa jogada o jogador obtém uma pontuação de 180 (60+60+60) pontos pois conseguiu 3 combinações de 3 peças em um mesmo movimento de peças.
A Capivara Apps está precisando de um programador para implementar o sistema de pontuação para o seu novo jogo. Você que curte um desafio, decidiu entrar nessa. Seu trabalho é descobrir a quantidade de pontos que o jogador vai ganhar ao fazer uma movimentação de uma peça no tabuleiro.
Entrada
Serão vários casos de teste a serem testados. Inicialmente dois valores inteiros N e M são informados (3 ≤ N e M ≤ 100), indicando o tamanho da matriz a ser lida que corresponde a um tabuleiro de jogo. Seguem-se N linhas com M colunas, com inteiros de 1 a 5 indicando as peças numeradas para cada posição do tabuleiro. Duas peças consecutivas na matriz são separadas por um espaço em branco e não podem existir posições no tabuleiro sem peças (número). Em seguida, são informados quatro valores inteiros I1, J1, I2 e J2 separados por um espaço (0 ≤ I1, I2 < N e 0 ≤ J1, J2 < M) indicando as posições das duas peças consecutivas a serem trocadas. As entradas terminam com o fim do arquivo. IMPORTANTE: Os tabuleiros lidos inicialmente não possuem combinações pré-existentes de 3 ou mais peças do mesmo tipo. As combinações só acontecem depois da movimentação das peças.
Saída
Para cada matriz lida, escrever uma linha com o número de pontos alcançados pelo jogador após executar a jogada de entrada de acordo com a tabela de pontuação apresentada, somando com a pontuação das possíveis novas combinações, caso existam, após a remoção das peças combinadas.
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
5 5 |
180 |