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.|

ILHAMG14 - A Ilha

Ana está desenvolvendo um jogo para celulares e tablets que é baseado no aquecimento global. No universo do jogo, o nível do mar está subindo de maneira extraordinariamente rápida. O jogador começa em uma ilha, e deve resgatar seus amigos e fugir da ilha antes que ela seja inteiramente engolida pelo mar.

Essa ilha é representada como um grid quadrado de n x n células. Cada célula é um quadrado de 1 metro de lado, e possui uma altura em relação ao nível original do mar que é dada por um número inteiro de metros.

O jogo ocorre em turnos. No primeiro turno, o mar está no nível zero. Sempre que há uma mudança de turno, o nível do mar sobe em 1 metro. Quando o nível do mar sobe, uma célula é alagada se (e somente se) a altura dela é menor ou igual ao novo nível do mar e ela é adjacente ao mar ou a uma célula alagada. Quando uma célula é alagada, células vizinhas que também estejam a uma altura menor ou igual ao nível atual do mar também serão alagadas, instantaneamente. Você pode considerar que a alteração no nível do mar (e o alagamento resultante) acontece de forma instantânea entre os turnos, i.e., após o fim do turno anterior mas antes do início do turno atual.

Ana recentemente terminou a primeira versão beta do jogo, e a distribuiu a alguns amigos para que eles o testassem. Algumas pessoas reclamaram que, em alguns mapas, o nível do mar sobe de maneira tal que em poucos turnos quase não há mais área não-alagada, e o jogo se torna muito difícil (ou impossível) de ganhar.

Ela está trabalhando arduamente em resolver o problema, mas precisa de uma forma de testar se as soluções que ela está implementando realmente funcionam. Por isso, ela pediu a sua ajuda. Dado um mapa, calcule qual é a área (em m^2) não-submersa da ilha no turno T.

Observações

Duas células do grid são adjacentes se e somente se elas compartilham uma aresta. Uma célula pode ter de 2 a 4 vizinhos (norte, sul, leste e oeste), sendo que apenas células da borda possuem menos do que 4 vizinhos.

Entrada

Há múltiplos casos de teste. Cada caso de teste começa com uma linha contendo dois inteiros N (0 < N ≤ 1024) e T. A ilha do jogo é um quadrado de N metros de lado, subdividido em N^2 células de 1 metro quadrado cada. Você deve calcular a área não submersa da ilha no turno T (1 ≤ T ≤ 255).

Em seguida, há N linhas, cada uma das quais contendo N inteiros, que representam a altura em metros de cada uma das células. Essa altura é um inteiro entre 1 e 255 (inclusive).

A entrada termina quando N = T = 0.

Saída

Para cada caso de teste, imprima uma linha contendo um único inteiro A, que é a área não-submersa da ilha após T turnos, em metros quadrados.

Exemplos

Entrada:
10 2
1 1 1 1 1 1 1 1 1 1
1 2 2 2 2 2 2 2 2 1
1 2 1 1 1 1 1 1 2 1
1 2 1 3 3 3 1 1 2 1
1 2 1 3 1 3 1 1 2 1
1 2 1 3 3 3 1 1 2 1
1 2 1 1 1 1 1 1 2 1
1 2 1 1 1 1 1 1 2 1
1 2 2 2 2 2 2 2 2 1
1 1 1 1 1 1 1 1 1 1
0 0

Saída:
64

No primeiro turno, o nível do mar é zero, e toda a ilha está acima dele. No segundo turno, o nível do mar passa a ser 1 metro, e todas as 36 células de altura 1 na borda da ilha são alagadas. Há outras células de altura 1 na ilha, mas elas não são alagadas porque estão protegidas do mar por “paredes” mais altas.


Adicionado por:Wanderley Guimarăes
Data:2014-07-10
Tempo limite:1s
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.