Aknakereső

(2020. december 25.)

Játszottál korábban aknavetőt? Nos, elhiszem, hogy igen, mindenki játszotta ezt a játékot gyermekkorunk alatt. De nem mindenki ismeri annak a fantasztikus játéknak a logikáját. Maradj velem ennél a bejegyzésnél, és hidd el, hogy egyszerűbbé teszem számodra, és szeretni fogod.

Kezdjük!

A aknavetős játékban háromféle sejtek, azaz megjelölve (az aknát vagy bombát tartalmazó sejtek), borított cellák, amelyek kattinthatók, fedetlen sejtek, amelyek már vannak kitéve.

Először bármely véletlenszerű cellára kattinthatunk, és ha sajnos egy enyém, a játékának vége. Ha a rákattintott cellán van egy szám, akkor ez azt jelzi, hogy ennek a cellának legfeljebb van ennyi aknája, amely körülveszi.

Egy cella lehetséges szomszédai

Egy cellának nyolc szomszédja van

Cella a rács (x, y) pozíciójában és a környező szomszédok

Vegyünk egy példát egy cellára, amelynek száma van ez.

A központi cellában 1-es számú van, vagyis legalább és legfeljebb egy enyém a környező szomszédokban.
Ez lehetséges bányapozíció lehet, és lehetséges helyes rácsot képvisel
Mivel a cellában 1 van, ez azt jelenti, hogy csak egy mérföld van ne mellette, de itt két aknát mutatunk be. Tehát ez nem lehetséges. Ez nem megfelelő rács.

Hasonlóképpen, példa két cellára, amelyeken van szám.

Ez érvényes. Mindkét cellának csak egy környező aknája lehet, és ez az aknák szomszédosak mindkét aknával.
Ez érvénytelen. Mindkét cellának csak egy környező aknája lehet, de itt mindkét cellának két szomszédos aknája van.

Most úgy gondolom, hogy megértette a logikát aknavető játék mögött. Tegyük fel, hogy egy kattintási pozíciót kap, és a lehető legnagyobb mértékben meg kell vizsgálnia az aknavető játék celláit.

Probléma-kimutatás (Forrás – Leetcode)

2D char mátrix, amely a játéktáblát ábrázolja. M egy unrevealed az enyém, E egy feltáratlan üres négyzet, B egy feltárt üres négyzetet, amelynek nincsenek szomszédos (fent, lent, balra, jobbra és mind a 4 átlós) aknák, számjegy (1 – 8) azt mutatja, hogy hány bánya szomszédos ezzel a feltárt négyzet, végül X egy kiderült az enyém.

Most megadva a következő kattintási pozíciót (sor- és oszlopindexek) az összes között unrevealed négyzetek (M vagy E), adja vissza a táblát, miután felfedte ezt a pozíciót a következő szabályok szerint:

Ha egy aknát (M) feltárnak, akkor a játéknak vége – módosítsa X értékre.

Ha egy üres négyzet (E) a nem találhatók szomszédos aknák , majd változtassa azt feltárt üresre (B) és az összes szomszédos unrevealed négyzeteket rekurzív módon kell feltárni.

Ha egy üres négyzet (E) a legalább egy szomszédos bánya feltárásra kerül, majd változtassa azt egy számjegyre (1 -ről 8 -ra), amely a szomszédos aknák számát jelöli.

Tegye vissza a táblát, ha már nem jelenik meg több négyzet.

Mélység első keresése – Önmagyarázó 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}

Funkció a tábla frissítésére a kattintás után

//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áselemzés

Időkomplexitás: O (m * n) legrosszabb esetben, ahol m a sorok száma és n az oszlopok száma.DFS-t hajtunk végre a rácson a kattintási pozícióból

Tér összetettsége: O (m * n ) verem a rekurzió számára

Srácok Nagyon remélem, hogy értékesnek találja ezt a cikket! Ha mégis van kérdése, akkor az alábbi megjegyzés szakaszban biztosan megvitathatja őket.

Nagyon köszönöm, hogy időt szentelt ennek a blognak.