Campo minado

(25 de dezembro de 2020)

Você já jogou caça-minas antes? Bem, eu acredito que sim, todo mundo jogou esse jogo durante a nossa infância. Mas nem todo mundo conhece a lógica por trás desse jogo incrível. Fique comigo neste post e acredite, vou torná-lo mais simples para você e você vai adorar.

Vamos começar!

No jogo de caça-minas, existem três tipos de células, isto é, marcadas (as células que contêm a minha ou bomba), células cobertas que são clicáveis, células descobertas que já estão expostas.

A princípio, podemos clicar em qualquer célula aleatória, e se infelizmente for uma mina, seu jogo acabou. Se a célula clicada tiver um número, isso denota que essa célula tem no máximo essas muitas minas ao seu redor.

Possíveis vizinhos de uma célula

Existem oito vizinhos para uma célula

Célula na posição (x, y) na grade e vizinhos ao redor

Vamos dar um exemplo de uma célula que tem um número ativado .

A célula central tem o número 1, o que significa que tem pelo menos e no máximo uma mina nos vizinhos próximos.
Esta pode ser uma possível posição da mina e representa uma possível grade correta
Como a célula tem 1, isso significa que há apenas um mi ne adjacente a ele, mas aqui duas minas são mostradas. Então, isso não é possível. Esta é a grade incorreta.

Da mesma forma, exemplo de duas células com um número.

Isso é válido. Ambas as células podem ter apenas 1 ao redor da mina e esta mina é adjacente a ambas as minas.
Isso é inválido. Ambas as células podem ter apenas 1 ao redor da mina, mas aqui ambas as células têm duas minas adjacentes nas vizinhas.

Agora, acho que você deve ter entendido a lógica atrás do jogo de caça-minas. Suponha que você receba uma posição de clique e tenha que explorar as células do jogo de caça-minas o máximo possível.

Declaração do problema (Fonte – Leetcode)

Você recebeu uma matriz de char 2D representando o tabuleiro de jogo. M representa um não revelado meu, E representa um não revelado quadrado vazio, B representa um revelou quadrado em branco sem minas adjacentes (acima, abaixo, à esquerda, à direita e nas 4 diagonais), dígito (1 a 8) representa quantas minas estão adjacentes a este revelado quadrado e, finalmente, X representa um revelou o meu.

Agora dada a próxima posição do clique (índices de linha e coluna) entre todos os não revelado quadrados (M ou E), retorne o tabuleiro após revelar esta posição de acordo com as seguintes regras:

Se uma mina (M) for revelada, o jogo acabou – altere-o para X .

Se um quadrado vazio (E) com nenhuma mina adjacente é revelada, em seguida, altere-o para o branco revelado (B) e todos os seus quadrados não revelados devem ser revelados recursivamente.

Se um quadrado vazio (E) com pelo menos uma mina adjacente é revelada e, em seguida, altere-a para um dígito (1 a 8) representando o número de minas adjacentes.

Retorne o tabuleiro quando nenhum quadrado mais for revelado.

Primeira pesquisa de profundidade – Código autoexplicativo

//all the possible 8 directions around a cell
private static int[] xdir = new int[]{-1, 1, -1, 1, -1, 1, 0, 0};
private static int[] ydir = new int[]{0, 0, -1, -1, 1, 1, -1, 1};
//checking if the adjacent position is a valid position or not
private boolean isValid(int newRow, int newCol, int rows, int cols){
return newRow>=0 && newRow=0 && newCol}

Função para atualizar a placa após o clique

//function to update the board based on the click
public char[][] updateBoard(char[][] board, int[] click) {
int rows = board.length;
int cols = board[0].length;

//if the click position is revealed or unrevealed mine, change it to revealed mine i.e. X and return the board as the game is over
if(board[click[0]][click[1]]=="M" || board[click[0]][click[1]]=="X"){
board[click[0]][click[1]] = "X";
return board;
}

//if the click position has an unrevealed cell, find the number of mines adjacent to it
int mines = 0;
for(int i=0; i<8; i++){
int newRow = click[0]+xdir[i];
int newCol = click[1]+ydir[i];

if(isValid(newRow, newCol, rows, cols) && board[newRow][newCol]=="M"){
mines++;
}
}

//if there is at least one mine adjacent to current click position, then update the board click position with the number of adjacent mines
//and in such case we won"t explore any further from current cell according to problem constraint and just return

if(mines>0){
board[click[0]][click[1]] = Character.forDigit(mines, 10);
return board;
}

//if there is no adjacent mine to the current click position, then mark this cell as revealed black cell
board[click[0]][click[1]] = "B";

//explore the adjacent valid unexplored cells which don"t have mine - DFS from current click position for all the valid cells
for(int i=0; i<8; i++){
int newRow = click[0]+xdir[i];
int newCol = click[1]+ydir[i];

if(isValid(newRow, newCol, rows, cols) && board[newRow][newCol]=="E"){
updateBoard(board, new int[]{newRow, newCol});
}
}

//return the final board
return board;
}

Análise de complexidade

Complexidade de tempo: O (m * n) no pior caso, onde m é o número de linhas e n é o número de colunas.Estamos realizando DFS na grade a partir da posição do clique

Complexidade do espaço: O (m * n ) empilhar espaço para recursão

Pessoal, realmente espero que vocês considerem este artigo valioso! Se ainda assim, você tem alguma dúvida, certamente pode discuti-la na seção de comentários abaixo.

Muito obrigado por dedicar seu tempo a este blog.