Mijnenveger

(25 dec.2020)

Heb je al eerder mijnenveger gespeeld? Nou, ik geloof van wel, iedereen heeft dat spel tijdens onze jeugd gespeeld. Maar niet iedereen kent de logica achter dat geweldige spel. Blijf bij me voor dit bericht en geloof me, ik zal het eenvoudiger voor je maken en je zult er dol op zijn.

Laten we beginnen!

In mijnenveger-spellen zijn er drie soorten cellen, dwz gemarkeerd (de cellen bevatten mijn of bom), bedekte cellen die klikbaar zijn, onbedekte cellen die al zichtbaar zijn.

In eerste instantie kunnen we op een willekeurige cel klikken, en als dat helaas zo is een mijn, je spel is voorbij. Als de aangeklikte cel een nummer bevat, geeft dit aan dat deze cel maximaal zoveel mijnen eromheen heeft.

Mogelijke buren van een cel

Er zijn acht buren voor een cel

Cel op positie (x, y) in het raster en omliggende buren

Laten we een voorbeeld nemen van een cel met een nummer op het.

Centrale cel heeft nummer 1 erop, dat betekent dat er minimaal en maximaal één mijn in de omliggende buren.
Dit kan een mogelijke mijnpositie zijn en het vertegenwoordigt een mogelijk correct rooster
Aangezien er 1 op de cel staat, betekent dit dat er maar één mi is ne ernaast, maar hier worden twee mijnen getoond. Dit is dus niet mogelijk. Dit is een onjuist raster.

Evenzo voorbeeld van twee cellen met een nummer erop.

Dit is geldig. Beide cellen kunnen slechts 1 omringende mijn hebben en deze mijn grenst aan beide mijnen.
Dit is ongeldig. Beide cellen kunnen slechts 1 omringende mijn hebben, maar hier hebben beide cellen twee aangrenzende mijnen in de buren.

Nu denk ik dat je de logica misschien hebt begrepen achter mijnenveger spel. Stel dat je een klikpositie krijgt en je moet de cellen van het mijnenveger-spel zoveel mogelijk verkennen.

Probleemstelling (Bron – Leetcode)

Je krijgt een 2D-tekenmatrix die het speelbord weergeeft. M staat voor een niet onthuld mijn, E vertegenwoordigt een niet onthuld leeg vierkant, B staat voor een onthulde leeg vierkant zonder aangrenzende (boven, onder, links, rechts en alle 4 diagonalen) mijnen, cijfer (1 tot 8) geeft aan hoeveel mijnen hieraan grenzen onthuld vierkant, en tot slot X vertegenwoordigt een onthulde de mijne.

Nu de volgende klikpositie gegeven (rij- en kolomindexen) tussen alle niet onthuld vierkanten (M of E), leg het bord terug nadat je deze positie onthuld hebt volgens de volgende regels:

Als een mijn (M) wordt onthuld, dan is het spel afgelopen – verander het in X .

Als een leeg vierkant (E) met geen aangrenzende mijnen is onthuld, verander deze dan in onthulde blanco (B) en alle aangrenzende unrevealed pleinen moeten recursief worden weergegeven.

Als een leeg vierkant (E) met ten minste één aangrenzende mijn wordt onthuld, verander het dan in een cijfer (1 tot 8) dat het aantal aangrenzende mijnen aangeeft.

Breng het bord terug als er geen vierkanten meer worden onthuld.

Diepte eerste zoekopdracht – Zelfverklarende code

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

Functie om het bord bij te werken na de 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;
}

Complexiteitsanalyse

Tijdscomplexiteit: O (m * n) in het ergste geval, waarbij m het aantal rijen is en n is het aantal kolommen.We voeren DFS uit op het raster vanuit de klikpositie

Ruimtecomplexiteit: O (m * n ) stapelruimte voor recursie

Jongens, ik hoop echt dat jullie dit artikel waardevol vinden! Als u nog vragen heeft, kunt u deze zeker bespreken in het commentaargedeelte hieronder.

Heel erg bedankt voor het besteden van uw tijd aan deze blog.