Saper

(25 grudnia 2020 r.)

Czy grałeś już wcześniej w trałowiec? Cóż, wierzę, że tak, wszyscy grali w tę grę w dzieciństwie. Ale nie wszyscy znają logikę tej niesamowitej gry. Zostań ze mną w sprawie tego posta i uwierz mi, ułatwię ci to i pokochasz to.

Zaczynamy!

W grze Saper są trzy rodzaje komórki, czyli oflagowane (komórki zawierające minę lub bombę), zakryte komórki, które można kliknąć, odsłonięte komórki, które są już naświetlone.

Na początku możemy kliknąć dowolną losową komórkę, a jeśli to niestety jest kopalnia, twoja gra jest skończona. Jeśli na klikniętej komórce znajduje się liczba, oznacza to, że komórka ma co najwyżej tylu otaczających ją min.

Możliwi sąsiedzi komórki

Komórka ma ośmiu sąsiadów

Komórka na pozycji (x, y) w siatce i sąsiednich sąsiadach

Weźmy przykład komórki, która ma numer

Centralna komórka ma numer 1, co oznacza, że ​​ma co najmniej i najwyżej jedna kopalnia w sąsiednich sąsiadach.
Może to być możliwa pozycja w kopalni i reprezentuje możliwą prawidłową siatkę
Ponieważ komórka ma 1, oznacza to, że jest tylko jedna mi ne obok niego, ale tutaj pokazano dwie miny. Więc to nie jest możliwe. To jest nieprawidłowa siatka.

Podobnie, przykład dwóch komórek z liczbą.

To jest poprawne. Obie komórki mogą mieć tylko jedną otaczającą minę, a ta kopalnia sąsiaduje z obiema minami.
To jest nieprawidłowe. Obie komórki mogą mieć tylko jedną otaczającą minę, ale tutaj obie komórki mają dwie sąsiadujące miny w sąsiadach.

Teraz myślę, że mógłbyś zrozumieć logikę za grą trałowców. Załóżmy, że masz jedno kliknięcie i musisz zbadać komórki trałowca tak bardzo, jak to możliwe.

Opis problemu (źródło – Leetcode)

Otrzymałeś macierz znaków 2D reprezentująca planszę do gry. M reprezentuje nieujawniony mine, E reprezentuje nieujawniony pusty kwadrat, B reprezentuje ujawniono pusty kwadrat bez sąsiadujących (powyżej, poniżej, lewej, prawej i wszystkich 4 przekątnych) min, cyfra (od „1” do „8”) oznacza liczbę min sąsiadujących z tym ujawnionym kwadrat, a na końcu X reprezentuje ujawniłem mine.

Biorąc pod uwagę następną pozycję kliknięcia (indeksy wierszy i kolumn) spośród wszystkich nieujawnione squares (M lub E), odłóż planszę po ujawnieniu tej pozycji zgodnie z następującymi zasadami:

Jeśli minie (M) zostanie odkryta, gra jest zakończona – zmień go na X .

Jeśli pusty kwadrat (E) z brak sąsiednich min jest ujawniony, a następnie zmień go na ujawnione puste („B”) i wszystkie sąsiednie nieujawnione kwadraty powinny być ujawniane rekurencyjnie.

Jeśli pusty kwadrat (E) z co najmniej jedna sąsiednia kopalnia zostanie ujawniona, a następnie zmień ją na cyfrę (od „1” do „8”) reprezentującą liczbę sąsiadujących min.

Zwróć planszę, gdy nie będzie już więcej kwadratów.

Pierwsze wyszukiwanie głębokości – kod wymagający wyjaśnienia

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

Funkcja aktualizacji tablicy po kliknięciu

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

Analiza złożoności

Złożoność czasowa: O (m * n) w najgorszym przypadku, gdzie m to liczba wierszy, a n to liczba kolumn.Wykonujemy DFS na siatce z pozycji kliknięcia

Złożoność przestrzeni: O (m * n ) miejsce na stosie rekursji

Chłopaki, naprawdę mam nadzieję, że ten artykuł okaże się wartościowy! Jeśli nadal masz jakieś pytania, z pewnością możesz je omówić w sekcji komentarzy poniżej.

Wielkie dzięki za poświęcenie czasu temu blogowi.