Démineur

(25 décembre 2020)

Avez-vous déjà joué au dragueur de mines? Eh bien, je crois que oui, tout le monde a joué à ce jeu pendant notre enfance. Mais tout le monde ne connaît pas la logique de ce jeu génial. Restez avec moi pour cet article et croyez-moi, je vais vous simplifier la tâche et vous allez ladorer.

Commençons!

Dans le jeu de dragueur de mines, il existe trois types de cellules, cest-à-dire marquées (les cellules contenant la mienne ou la bombe), les cellules couvertes qui sont cliquables, les cellules non couvertes qui sont déjà exposées.

Dans un premier temps, nous pouvons cliquer sur nimporte quelle cellule aléatoire, et si malheureusement cest une mine, votre jeu est terminé. Si la cellule sur laquelle vous avez cliqué comporte un numéro, cela signifie que cette cellule a au plus ces nombreuses mines qui lentourent.

Voisins possibles dune cellule

Il y a huit voisins pour une cellule

Cellule à la position (x, y) dans la grille et les voisins environnants

Prenons un exemple de cellule qui a un nombre sur

La cellule centrale a le numéro 1, cela signifie quelle a au moins et au plus une mine dans ses voisins environnants.
Cela peut être une position de mine possible et cela représente une grille correcte possible
Comme la cellule a 1 dessus, cela signifie quil ny a quun mi ne adjacent, mais ici deux mines sont représentées. Donc, ce nest pas possible. Cette grille est incorrecte.

De même, exemple de deux cellules comportant un nombre.

Ceci est valide. Les deux cellules ne peuvent avoir quune seule mine environnante et cette mine est adjacente aux deux mines.
Ceci nest pas valide. Les deux cellules ne peuvent avoir quune seule mine environnante, mais ici les deux cellules ont deux mines adjacentes dans les voisins.

Maintenant, je pense que vous avez peut-être compris la logique derrière le jeu de dragueur de mines. Supposons que lon vous donne une position de clic et que vous devez explorer les cellules du jeu de dragueur de mines autant que possible.

Problème (Source – Leetcode)

On vous donne une matrice de caractères 2D représentant le plateau de jeu. M représente un non révélé le mien, E représente un non révélé carré vide, B représente un a révélé un carré vide qui na pas de mines adjacentes (au-dessus, en dessous, à gauche, à droite et les 4 diagonales), le chiffre (1 à 8) représente le nombre de mines adjacentes à ce révélé carré, et enfin X représente un a révélé le mien .

Maintenant, la position du clic suivant (index de ligne et de colonne) parmi tous les non révélé carrés (M ou E), retournez le plateau après avoir révélé cette position selon les règles suivantes:

Si une mine (M) est révélée, alors la partie est terminée – changez-le en X .

Si un carré vide (E) avec aucune mine adjacente est révélée, puis changez-le en blanc révélé (B) et tous ses unrevealed les carrés doivent être révélés récursivement.

Si un carré vide (E) avec au moins une mine adjacente est révélée, puis changez-la en un chiffre (1 à 8) représentant le nombre de mines adjacentes.

Renvoyez le tableau lorsque plus aucun carré ne sera révélé.

Première recherche en profondeur – Code explicite

//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}

Fonction de mise à jour de la carte après le 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;
}

Analyse de complexité

Complexité temporelle: O (m * n) dans le pire des cas, où m est le nombre de lignes et n est le nombre de colonnes.Nous exécutons DFS sur la grille à partir de la position du clic

Complexité de lespace: O (m * n ) espace de pile pour la récursivité

Les gars Jespère vraiment que vous trouverez cet article précieux! Si vous avez encore des questions, vous pouvez sûrement en discuter dans la section commentaires ci-dessous.

Merci beaucoup davoir consacré votre temps à ce blog.