Hledání min

(25. prosince 2020)

Hráli jste už minolovky? Věřím, že ano, každý hrál tuto hru během našeho dětství. Ale ne každý zná logiku této úžasné hry. Zůstaňte u mě u tohoto příspěvku a věřte mi, že vám to zjednoduším a budete to milovat.

Začněme!

Ve hře Hledání min existují tři typy buňky, tj. označené (buňky obsahující minu nebo bombu), zakryté buňky, na které lze kliknout, nekryté buňky, které jsou již vystaveny.

Nejprve můžeme kliknout na libovolnou náhodnou buňku, a pokud je důl, vaše hra skončila. Pokud má buňka, na kterou se kliklo, číslo, znamená to, že tato buňka má maximálně tolik těchto dolů, které ji obklopují.

Možní sousedé buňky

Existuje osm sousedů buňky

Buňka na pozici (x, y) v mřížce a okolní sousedé

Vezměme si příklad buňky, která má číslo na it.

Centrální buňka má číslo 1, to znamená, že má alespoň a maximálně jeden důl v okolních sousedech.
Může se jednat o možnou pozici dolu a představuje možnou správnou mřížku
Jelikož má buňka 1, znamená to, že existuje pouze jeden mi sousedí s ním, ale zde jsou zobrazeny dva doly. To tedy není možné. Toto je nesprávná mřížka.

Podobně příklad dvou buněk, které mají na sobě číslo.

Toto je platné. Obě buňky mohou mít pouze 1 okolní důl a tento důl sousedí s oběma doly.
Toto je neplatné. Obě buňky mohou mít pouze 1 okolní důl, ale zde mají obě buňky dva sousední doly u sousedů.

Myslím, že jste pochopili logiku za minolovkou. Předpokládejme, že dostanete jedno kliknutí a musíte co nejvíce prozkoumat buňky hry Hledání min.

Prohlášení o problému (zdroj – Leetcode)

Dostanete 2D char matice představující herní plán. M představuje neobjevený důl, E představuje neobjevený prázdný čtverec, B představuje odhalil prázdný čtverec, který nemá žádné sousední (nad, pod, vlevo, vpravo a všechny 4 úhlopříčky) miny, číslice (1 až 8) představuje počet min sousedících s tímto odhaleným čtverec a nakonec X představuje odhaleno moje.

Nyní je uvedena pozice dalšího kliknutí (indexy řádků a sloupců) mezi všemi nezveřejněno čtverce („M“ nebo „E“), vraťte herní plán po odhalení této pozice podle následujících pravidel:

Pokud je odhalen důl („M“), hra končí – změňte jej na X .

Pokud je prázdný čtverec (E) s nejsou odhaleny žádné sousední doly , poté jej změňte na odhalený blank (B) a všechny jeho sousední neobjevené čtverce by měly být odhaleny rekurzivně.

Pokud je prázdný čtverec (E) s je odhalen alespoň jeden sousední důl , který poté změňte na číslici (1 až 8) představující počet sousedních dolů.

Pokud již nebudou odhaleny žádné čtverce, vraťte desku.

Hledání hloubky prvního textu – vysvětlující kód

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

Funkce pro aktualizaci desky po kliknutí

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

Analýza složitosti

Časová složitost: O (m * n) v nejhorším případě, kde m je počet řádků a n je počet sloupců.DFS provádíme na mřížce z pozice kliknutí

Prostorová složitost: O (m * n ) zásobníkový prostor pro rekurzi

Kluci, opravdu doufám, že tento článek bude pro vás cenný! Pokud stále máte nějaké dotazy, určitě o nich můžete diskutovat v sekci komentářů níže.

Děkujeme, že jste se tomuto blogu věnovali.