Buscaminas

(25 de diciembre de 2020)

¿Has jugado al buscaminas antes? Bueno, creo que sí, todo el mundo ha jugado ese juego durante nuestra infancia. Pero no todo el mundo conoce la lógica detrás de ese increíble juego. Quédate conmigo para esta publicación y créeme, te lo haré más sencillo y te va a encantar.

¡Empecemos!

En el juego buscaminas, hay tres tipos de celdas, es decir, marcadas (las celdas que contienen mina o bomba), celdas cubiertas en las que se puede hacer clic, celdas descubiertas que ya están expuestas.

Al principio, podemos hacer clic en cualquier celda aleatoria, y si desafortunadamente es una mía, tu juego se acabó. Si la celda en la que se hizo clic tiene un número, indica que esta celda tiene como máximo estas muchas minas a su alrededor.

Posibles vecinos de una celda

Hay ocho vecinos para una celda

Celda en la posición (x, y) en la cuadrícula y vecinos circundantes

Tomemos un ejemplo de una celda que tiene un número en

La celda central tiene el número 1, eso significa que tiene al menos y como máximo una mina en sus vecinos circundantes.
Esta puede ser una posible posición de la mina y representa una posible cuadrícula correcta
Como la celda tiene 1, eso significa que solo hay un mi ne adyacente a él, pero aquí se muestran dos minas. Entonces, esto no es posible. Esta es una cuadrícula incorrecta.

De manera similar, ejemplo de dos celdas que tienen un número.

Esto es válido. Ambas celdas solo pueden tener una mina circundante y esta mina es adyacente a ambas minas.
Esto no es válido. Ambas celdas pueden tener solo 1 mina alrededor, pero aquí ambas celdas tienen dos minas adyacentes en las vecinas.

Ahora, creo que puede que hayas entendido la lógica detrás del juego del buscaminas. Suponga que se le da la posición de un clic y tiene que explorar las celdas del juego buscaminas tanto como sea posible.

Enunciado del problema (Fuente – Leetcode)

Se le da una matriz de caracteres 2D que representa el tablero de juego. M representa un no revelado mío, E representa un no revelado cuadrado vacío, B representa un reveló un cuadrado en blanco que no tiene minas adyacentes (arriba, abajo, izquierda, derecha y las 4 diagonales), dígito (1 a 8) representa cuántas minas hay adyacentes a este revelado cuadrado y, finalmente, X representa un reveló mío.

Ahora, dada la siguiente posición de clic (índices de fila y columna) entre todos los cuadrados (M o E), devuelve el tablero después de revelar esta posición de acuerdo con las siguientes reglas:

Si se revela una mina (M), entonces el juego termina – cámbielo a X .

Si un cuadrado vacío (E) con no se revelan minas adyacentes , luego cámbielo a blanco revelado (B) y todas sus no revelados los cuadrados deben revelarse de forma recursiva.

Si un cuadrado vacío (E) con se revela al menos una mina adyacente , luego cámbiela a un dígito (1 a 8) que represente el número de minas adyacentes.

Devuelve el tablero cuando no se muestren más cuadrados.

Profundidad de búsqueda inicial: 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}

Función para actualizar la placa después del clic

//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álisis de complejidad

Complejidad de tiempo: O (m * n) en el peor de los casos, donde m es el número de filas y n es el número de columnas.Realizamos DFS en la cuadrícula desde la posición del clic

Complejidad espacial: O (m * n ) espacio de pila para recursividad

¡Chicos, realmente espero que encuentren este artículo valioso! Si aún tiene alguna consulta, seguramente puede discutirlas en la sección de comentarios a continuación.

Muchas gracias por dedicar su tiempo a este blog.