Minensuchboot

(25. Dezember 2020)

Haben Sie schon einmal Minensuchboot gespielt? Nun, ich glaube ja, jeder hat dieses Spiel in unserer Kindheit gespielt. Aber nicht jeder kennt die Logik hinter diesem großartigen Spiel. Bleib bei mir für diesen Beitrag und glaub mir, ich werde es dir einfacher machen und du wirst es lieben.

Fangen wir an!

Im Minensuchspiel gibt es drei Arten von Zellen, dh markiert (die Zellen, die Mine oder Bombe enthalten), bedeckte Zellen, die anklickbar sind, unbedeckte Zellen, die bereits freigelegt sind.

Zuerst können wir auf jede zufällige Zelle klicken, und wenn dies leider der Fall ist eine Mine, dein Spiel ist vorbei. Wenn die angeklickte Zelle eine Nummer enthält, bedeutet dies, dass diese Zelle höchstens diese vielen Minen umgibt.

Mögliche Nachbarn einer Zelle

Es gibt acht Nachbarn für eine Zelle

Zelle an Position (x, y) im Raster und den umgebenden Nachbarn

Nehmen wir ein Beispiel für eine Zelle mit einer Nummer it.

Die zentrale Zelle hat die Nummer 1, dh sie hat mindestens und höchstens Eine Mine in den umliegenden Nachbarn.
Dies kann eine mögliche Minenposition sein und stellt ein mögliches korrektes Raster dar
Da die Zelle 1 enthält, bedeutet dies, dass nur eine Meile vorhanden ist ne daneben, aber hier sind zwei minen gezeigt. Das ist also nicht möglich. Dies ist ein falsches Raster.

Ähnlich ein Beispiel für zwei Zellen mit einer Nummer.

Dies ist gültig. Beide Zellen können nur 1 umgebende Mine haben und diese Mine grenzt an beide Minen.
Dies ist ungültig. Beide Zellen können nur eine umgebende Mine haben, aber hier haben beide Zellen zwei benachbarte Minen in den Nachbarn.

Nun, ich denke, Sie haben die Logik vielleicht verstanden hinter Minensuchbootspiel. Angenommen, Sie erhalten eine Klickposition und müssen die Zellen des Minensuchspiels so weit wie möglich erkunden.

Problemstellung (Quelle – Leetcode)

Sie erhalten eine 2D-Zeichenmatrix, die das Spielbrett darstellt. M repräsentiert eine nicht enthüllte meins, E repräsentiert eine nicht enthüllte leeres Quadrat, B repräsentiert ein enthüllte leeres Quadrat ohne benachbarte Minen (oben, unten, links, rechts und alle 4 Diagonalen), Ziffer (1 bis 8) gibt an, wie viele Minen neben dieser Quadrat und schließlich X repräsentiert ein enthüllte meins.

Nun wird die nächste Klickposition (Zeilen- und Spaltenindizes) unter allen angegeben nicht enthüllt Quadrate (M oder E), gib das Brett zurück, nachdem du diese Position gemäß den folgenden Regeln enthüllt hast:

Wenn eine Mine (M) aufgedeckt wird, ist das Spiel vorbei – Ändern Sie es in X .

Wenn ein leeres Quadrat (E) mit Es werden keine benachbarten Minen angezeigt. Ändern Sie sie dann in „Blank“ (B) und alle benachbarten nicht enthüllte Quadrate sollten rekursiv aufgedeckt werden.

Wenn ein leeres Quadrat (E) mit Mindestens eine benachbarte Mine wird aufgedeckt und in eine Ziffer (1 bis 8) geändert, die die Anzahl benachbarter Minen darstellt.

Geben Sie die Tafel zurück, wenn keine Quadrate mehr angezeigt werden.

Tiefe erste Suche – Selbsterklärender 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}

Funktion zum Aktualisieren der Karte nach dem Klicken

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

Komplexitätsanalyse

Zeitkomplexität: O (m * n) im schlimmsten Fall, wobei m die Anzahl der Zeilen und ist n ist die Anzahl der Spalten.Wir führen DFS auf dem Raster von der Klickposition aus durch.

Raumkomplexität: O (m * n ) Stapelplatz für Rekursion

Leute, ich hoffe wirklich, dass Sie diesen Artikel wertvoll finden! Wenn Sie dennoch Fragen haben, können Sie diese sicherlich im Kommentarbereich unten diskutieren.

Vielen Dank, dass Sie sich mit diesem Blog beschäftigt haben.