Minesveger

(25. dec 2020)

Har du spillet minesveger før? Nå, jeg tror ja, alle har spillet det spil i vores barndom. Men ikke alle kender logikken bag det fantastiske spil. Bliv hos mig til dette indlæg og tro mig, jeg vil gøre det enklere for dig, og du vil elske det.

Lad os begynde!

I minesveger-spil er der tre typer celler, dvs. markerede (cellerne, der indeholder mine eller bombe), dækkede celler, der er klikbare, udækkede celler, der allerede er eksponeret.

Først kan vi klikke på en vilkårlig celle, og hvis det desværre er en mine, dit spil er slut. Hvis den celle, der er klikket på, har et nummer på sig, angiver det, at denne celle højst har disse mange miner, der omgiver den.

Mulige naboer til en celle

Der er otte naboer til en celle

Celle ved position (x, y) i gitteret og omgivende naboer

Lad os tage et eksempel på en celle, der har et tal på det.

Central celle har nummer 1 på sig, det betyder, at det har mindst og højst en mine i de omkringliggende naboer.
Dette kan være en mulig mineposition, og det repræsenterer et muligt korrekt gitter
Da cellen har 1 på sig, betyder det, at der kun er en mi ne støder op til det, men her vises to miner. Så dette er ikke muligt. Dette er forkert gitter.

Tilsvarende eksempel på to celler med et nummer på sig.

Dette er gyldigt. Begge celler kan kun have 1 omgivende mine, og denne mine støder op til begge miner.
Dette er ugyldigt. Begge celler kan kun have 1 omgivende mine, men her har begge celler to tilstødende miner i naboerne.

Nu tror jeg, du måske har forstået logikken bag minesveger-spil. Antag, du får position med et klik, og du skal udforske cellerne i minesveger-spil så meget som muligt.

Problemangivelse (Kilde – Leetcode)

Du får en 2D-træmatrix, der repræsenterer spillebrættet. M repræsenterer en ikke afsløret mine, E repræsenterer en ikke afsløret tom firkant, B repræsenterer en afsløret blank firkant, der ikke har nogen tilstødende (over, under, venstre, højre og alle 4 diagonaler) miner, ciffer (1 til 8) repræsenterer hvor mange miner der støder op til denne afsløret firkant, og til sidst X repræsenterer en afsløret mine.

Nu givet næste klikposition (række- og kolonneindeks) blandt alle ikke afsløret firkanter (M eller E), returner brættet efter at have afsløret denne position i henhold til følgende regler:

Hvis en mine (M) afsløres, er spillet slut – skift til X .

Hvis en tom firkant (E) med ingen nærliggende miner afsløres, og skift den derefter til afsløret blank (B) og alle dens tilstødende unrevealed firkanter skal afsløres rekursivt.

Hvis en tom firkant (E) med mindst en tilstødende mine afsløres, og skift den derefter til et ciffer (1 til 8), der repræsenterer antallet af tilstødende miner.

Returner tavlen, når der ikke vises flere firkanter.

Dybde Første søgning – Selvforklarende kode

//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 til opdatering af tavlen efter klik

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

Kompleksitetsanalyse

Tidskompleksitet: O (m * n) i værste fald, hvor m er antallet af rækker og n er antallet af kolonner.Vi udfører DFS på gitteret fra klikpositionen

Rumkompleksitet: O (m * n ) stak plads til rekursion

Gutter Jeg håber virkelig, at du finder denne artikel værdifuld! Hvis du stadig har spørgsmål, kan du helt sikkert diskutere dem i kommentarfeltet nedenfor.

Mange tak for at du har brugt din tid til denne blog.