Minesvepare

(25 dec 2020)

Har du spelat minesvepare tidigare? Jag tror ja, alla har spelat det spelet under vår barndom. Men inte alla känner till logiken bakom det fantastiska spelet. Stanna hos mig för det här inlägget och tro mig att jag kommer att göra det enklare för dig och du kommer att älska det.

Låt oss börja!

I minesveparspel finns det tre typer av celler, dvs. flaggade (cellerna som innehåller min eller bomb), täckta celler som är klickbara, avtäckta celler som redan är exponerade.

Först kan vi klicka på valfri slumpmässig cell, och om det tyvärr är en gruva, ditt spel är över. Om den klickade cellen har ett nummer på sig anger det att den här cellen har högst dessa många gruvor som omger den.

Möjliga grannar till en cell

Det finns åtta grannar för en cell

Cell vid position (x, y) i rutnätet och omgivande grannar

Låt oss ta ett exempel på en cell som har ett nummer på det.

Centralcell har nummer 1 på sig, det betyder att det har åtminstone och högst en gruva i dess omgivande grannar.
Detta kan vara en möjlig minposition och det representerar ett möjligt korrekt rutnät
Eftersom cellen har 1 på betyder det att det bara finns en mi ne intill den, men här visas två gruvor. Så detta är inte möjligt. Detta är felaktigt rutnät.

På samma sätt exempel på två celler som har ett nummer på sig.

Detta är giltigt. Båda cellerna kan bara ha en omgivande gruva och den här gruvan ligger intill båda gruvorna.
Detta är ogiltigt. Båda cellerna kan bara ha en omgivande gruva men här har båda cellerna två angränsande gruvor i grannarna.

Nu tror jag att du kanske har förstått logiken bakom minesveparspel. Antag att du får en klickposition och du måste utforska cellerna i minesveparspel så mycket som möjligt.

Problemförklaring (Källa – Leetcode)

Du får en 2D-matris som representerar spelbrädet. M representerar en oöppnad min, E representerar en oöppnad tomt kvadrat, B representerar en avslöjade tomt kvadrat som inte har några intilliggande (ovan, under, vänster, höger och alla 4 diagonaler) gruvor, siffra (1 till 8) representerar hur många gruvor som gränsar till denna avslöjade kvadrat och slutligen X representerar en avslöjade min.

Nu ges nästa klickposition (rad- och kolumnindex) bland alla oöppnad kvadrater (M eller E), returnera brädet efter att ha avslöjat denna position enligt följande regler:

Om en gruva (M) avslöjas är spelet över – ändra det till X .

Om en tom fyrkant (E) med inga angränsande gruvor avslöjas, ändra det sedan till avslöjat tomt (B) och alla dess intilliggande oöppnade rutor ska avslöjas rekursivt.

Om en tom fyrkant (E) med minst en intilliggande gruva avslöjas och ändra den sedan till en siffra (1 till 8) som representerar antalet intilliggande gruvor.

Returnera tavlan när inga fler rutor kommer att avslöjas.

Djup Första sökning – Självförklarande kod

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

Funktion för att uppdatera brädet efter klick

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

Komplexitetsanalys

Tidskomplexitet: O (m * n) i värsta fall, där m är antalet rader och n är antalet kolumner.Vi utför DFS i rutnätet från klickpositionen

Rymdkomplexitet: O (m * n ) stack utrymme för rekursion

Killar Jag hoppas verkligen att du tycker att den här artikeln är värdefull! Om du fortfarande har frågor kan du säkert diskutera dem i kommentarsektionen nedan.

Tack så mycket för att du ägnar din tid åt den här bloggen.