O Famoso Campo Minado

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 minas 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ções, em relação a um conjunto de quadrados adjacentes a algum quadrado sendo analisado:

• Quando o número de quadrados cobertos (adjCob), somado do número de quadrados sinalizados (adjSin) for igual à dica (adjCob + adjSin = dica), então todos os quadrados cobertos contém minas.
• Quando o número de de quadrados sinalizados (adjSin) for igual à dica (adjSin = dica), então todos os quadrados cobertos não contém minas.

Veja como exemplo na Figura 2.

Na parte a) da figura, temos adjCob = 1, adjSin = 0 e dica = 1, logo 1 + 0 = 1, e podemos sinalizar os quadrados cobertos para identificar as minas.

Na parte b) da figura, temos adjSin = 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.