Campo Minato

(25 dicembre 2020)

Hai mai giocato a Campo Minato? Beh, credo di sì, tutti hanno giocato a quel gioco durante la nostra infanzia. Ma non tutti conoscono la logica dietro questo fantastico gioco. Resta con me per questo post e credimi, ti renderò tutto più semplice e lo adorerai.

Cominciamo!

Nel gioco del campo minato, ci sono tre tipi di celle, cioè contrassegnate (le celle che contengono la mia o la bomba), celle coperte che sono cliccabili, celle scoperte che sono già esposte.

Allinizio possiamo fare clic su qualsiasi cella casuale, e se sfortunatamente è una miniera, il tuo gioco è finito. Se la cella su cui si è fatto clic ha un numero, significa che questa cella ha al massimo queste numerose mine che la circondano.

Possibili vicini di una cella

Ci sono otto vicini per una cella

Cella in posizione (x, y) nella griglia e adiacenti circostanti

Facciamo un esempio di una cella che ha un numero su it.

La cella centrale ha il numero 1, il che significa che ha almeno e al massimo una miniera nelle vicinanze.
Questa può essere una possibile posizione della miniera e rappresenta una possibile griglia corretta
Dato che la cella ha 1 su di essa, significa che cè solo un mi ne adiacente, ma qui vengono mostrate due mine. Quindi questo non è possibile. Questa è una griglia errata.

Allo stesso modo, esempio di due celle con un numero sopra.

Questo è valido. Entrambe le celle possono avere solo 1 miniera circostante e questa miniera è adiacente a entrambe le miniere.
Questo non è valido. Entrambe le celle possono avere solo 1 miniera circostante, ma qui entrambe le celle hanno due miniere adiacenti nei vicini.

Ora, penso che potresti aver capito la logica dietro il gioco del dragamine. Supponiamo che ti venga assegnata una posizione di clic e che tu debba esplorare il più possibile le celle del gioco del dragamine.

Dichiarazione del problema (Fonte – Leetcode)

Ti viene dato una matrice di caratteri 2D che rappresenta il tabellone di gioco. M rappresenta un non rivelato mio, E rappresenta un non rivelato quadrato vuoto, B rappresenta un ha rivelato quadrato vuoto che non ha mine adiacenti (sopra, sotto, sinistra, destra e tutte e 4 le diagonali), digit (da 1 a 8) rappresenta il numero di mine adiacenti a questo rivelato quadrato e infine ” X “ rappresenta un ha rivelato mio.

Ora data la posizione del clic successivo (indici di riga e colonna) tra tutti i non rivelato caselle (M o E), restituisci il tabellone dopo aver rivelato questa posizione secondo le seguenti regole:

Se viene scoperta una mina (M), il gioco è finito modificalo in X .

Se un quadrato vuoto (E) con nessuna miniera adiacente viene rivelata, quindi modificala in vuota rivelata (“B”) e tutte le i quadrati non rivelati devono essere rivelati in modo ricorsivo.

Se un quadrato vuoto (E) con viene rivelata almeno una miniera adiacente , quindi modificala in una cifra (da “1” a “8”) che rappresenta il numero di mine adiacenti.

Restituisci il tabellone quando non verranno più rivelati quadrati.

Profondità prima ricerca – Codice autoesplicativo

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

Funzione per aggiornare la scheda dopo il 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;
}

Analisi della complessità

Complessità temporale: O (m * n) nel caso peggiore, dove m è il numero di righe e n è il numero di colonne.Stiamo eseguendo DFS sulla griglia dalla posizione del clic

Space Complexity: O (m * n ) impila lo spazio per la ricorsione

Ragazzi, spero davvero che questo articolo sia prezioso! Se hai ancora delle domande, puoi sicuramente discuterne nella sezione commenti qui sotto.

Grazie mille per aver dedicato il tuo tempo a questo blog.