Minesveiper

(25. des 2020)

Har du spilt minesveiper før? Vel, jeg tror ja, alle har spilt det spillet i barndommen vår. Men ikke alle kjenner logikken bak det fantastiske spillet. Bli med meg for dette innlegget og tro meg at jeg vil gjøre det enklere for deg, og du kommer til å elske det.

La oss begynne!

I minesveiper-spillet er det tre typer celler, dvs. flaggede (cellene som inneholder mine eller bombe), tildekkede celler som er klikkbare, avdekkede celler som allerede er eksponert.

Først kan vi klikke på en hvilken som helst tilfeldig celle, og hvis det dessverre er en gruve, spillet ditt er over. Hvis den klikkte cellen har et tall, angir den at denne cellen har maksimalt disse mange gruvene rundt den.

Mulige naboer til en celle

Det er åtte naboer for en celle

Celle i posisjon (x, y) i rutenettet og omkringliggende naboer

La oss ta et eksempel på en celle som har et tall på den.

Sentralcelle har nummer 1 på seg, det betyr at den har minst og høyst en gruve i de omkringliggende naboene.
Dette kan være en mulig gruveposisjon og det representerer et mulig riktig rutenett
Ettersom cellen har 1 på seg, betyr det at det bare er en mi ne ved siden av den, men her vises to miner. Så dette er ikke mulig. Dette er feil rutenett.

Tilsvarende eksempel på to celler som har et nummer på seg.

Dette er gyldig. Begge cellene kan bare ha en omliggende gruve, og denne gruven ligger ved siden av begge gruvene.
Dette er ugyldig. Begge cellene kan bare ha en omliggende gruve, men her har begge cellene to nærliggende miner i naboene.

Nå tror jeg du kanskje har forstått logikken bak minesveiper-spillet. Anta at du får posisjon med ett klikk, og at du må utforske cellene i minesveiper-spillet så mye som mulig.

Problemstilling (Kilde – Leetcode)

Du får en 2D-røde matrise som representerer spillbrettet. M representerer en ikke avslørt mine, E representerer en ikke avslørt tom firkant, B representerer en avslørt tomt firkant som ikke har noen tilstøtende (over, under, venstre, høyre og alle 4 diagonaler) gruver, siffer (1 til 8) representerer hvor mange gruver som grenser til denne avslørt kvadrat, og til slutt X representerer en avslørt mine.

Nå gitt neste klikkposisjon (rad- og kolonneindekser) blant alle uavdekket firkanter (M eller E), returner brettet etter å ha avslørt denne posisjonen i henhold til følgende regler:

Hvis en gruve (M) blir avslørt, er spillet over – endre den til X .

Hvis en tom firkant (E) med ingen tilstøtende miner blir avslørt, og endre det til avslørt tomt (B) og alle dets tilstøtende uavdekket firkanter bør avsløres rekursivt.

Hvis en tom firkant (E) med minst en tilstøtende gruve blir avslørt, og endre den til et siffer (1 til 8) som representerer antall tilstøtende miner.

Returner tavlen når ikke flere firkanter blir avslørt.

Dybde første søk – 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}

Funksjon for å oppdatere brettet etter klikk

//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 verste fall, hvor m er antall rader og n er antall kolonner.Vi utfører DFS på rutenettet fra klikkposisjonen

Plasskompleksitet: O (m * n ) stable plass for rekursjon

Gutter Jeg håper virkelig at du synes denne artikkelen er verdifull! Hvis du fortsatt har spørsmål, kan du sikkert diskutere dem i kommentarseksjonen nedenfor.

Tusen takk for at du har viet tiden din til denne bloggen.