uCoder | 1170 | Nível: 5 | Tempo Limite: 10
O Famoso Campo Minado
Adaptado por erich.rodriguesf
Campo Minado é um jogo antigo, que ficou muito conhecido por ser um jogo nativo em um sistema operacional que ninguém lembra o nome. Trata-se de uma grade com N linhas e M colunas, contendo diversas minas espalhadas, e diversas dicas indicando onde elas estariam. O seu objetivo é encontrar todas as minas, sem nunca pisar em uma.
Cada posição da grade pode ou não conter uma mina. Caso não contenha uma mina, tal posição irá conter um valor, conhecido também como dica, que irá identificar quantas minas há nos quadrados adjacentes àquele (nas 8 direções), que varia de 0 a 8 (ver Figura 1).
Rafael se interessou muito pela proposta do jogo, e achou tão fácil que resolveu escrever por conta própria alguns casos de jogo, onde ele define onde as bombas estarão e quais as dicas iniciais. Notou porém que existem duas situações que podem ocorrer durante a partida: em determinados casos, é possível descobrir com certeza onde está a mina, graças às dicas dadas; já em outros casos, não é possível descobrir com certeza onde está a mina, e o jogador vai depender apenas de sua sorte.
Considere uma partida como se segue: há inicialmente um determinado número de quadrados revelados (dicas) e o restante dos quadrados cobertos. O jogador pode então realizar dois movimentos: revelar um quadrado coberto, podendo encontrar uma mina (fim de jogo) ou uma dica; ou sinalizar um quadrado coberto como sendo uma mina, de modo a prevenir a si mesmo de nunca revelar tal quadrado.
Para prosseguir na partida de uma forma lógica (sem se basear na sorte), leve em consideração as seguintes definiçoes:
- É possível sinalizar uma mina quando o número de quadrados adjacentes cobertos (adjCob) somado do número de minas sinalizadas nos quadrados adjacentes (adjMin) é igual ao número da dica do quadrado atual (dica).
- É possível revelar um quadrado adjacente quando o número da dica do quadrado atual (dica) é igual ao número de minas sinalizadas nos quadrados adjacentes (adjMin).
Veja como exemplo na Figura 2.Na parte a) da figura, temos adjCob = 1, adjMin = 0 e dica = 1, logo 1 + 0 = 1, e podemos sinalizar os quadrados cobertos para identificar as minas.
Na parte b) da figura, temos adjMin = 1 e dica = 1, logo 1 = 1, e podemos revelar os quadrados adjacentes ainda cobertos.
Para que seu caso de jogo ficasse interessante e desafiador, Rafael decidiu que devia ser possível encontrar todas as minas baseando-se apenas na definição dada, porém não sabe verificar quando isso é possível, e para isso pediu sua ajuda.
Entrada
A entrada irá conter diversos casos de teste. Cada caso de teste inicia com três inteiros N, M e K (1 <= N, M <= 20, 1 <= K <= 30), indicando que a grade do jogo contém N linhas e M colunas, e que há K minas escondidas naquela grade. Em seguida, haverá N linhas com M caracteres em cada linha, onde o caractere da linha i e coluna j (1 <= i <= N e 1 <= j <= M) indica o que há na posição i, j da grade:
'.' - Quadrado coberto.
Um inteiro entre 0 e 8 – Quadrado revelado, onde o valor é a dica.
Em seguida haverá K pares de inteiros a e b (1 <= a <= N e 1 <= b <= M), indicando que há uma mina na posição a, b da grade. Note que tal informação é útil quando um quadrado é revelado, para poder calcular qual a dica que será apresentada.
A entrada termina quando N = M = K = 0.
Saída
Seu programa deverá imprimir, para cada caso de teste, uma linha, contendo a frase “Possivel” caso seja possível encontrar todas as minas baseando nas definições acima, ou “Impossivel”, caso isso não seja possível.
Notas
Quando um quadrado é revelado, o valor apresentado (dica) é calculado a partir do número de minas nos quadrados adjacentes ao mesmo.
Quando um quadrado com a dica 0 é revelado, todos os quadrados cobertos adjacentes são revelados, uma vez que é certo que nenhum deles é uma mina.
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
4 4 3 |
Possivel |