Miinanraivaaja

(25. joulukuuta 2020)

Oletko pelannut miinanraivaajaa aiemmin? Uskon kyllä, kaikki ovat pelanneet tätä peliä lapsuutemme aikana. Mutta kaikki eivät tiedä sen mahtavan pelin logiikkaa. Pysy kanssani tätä viestiä varten ja uskokaa, että teen sen yksinkertaisemmaksi sinulle ja tulet rakastamaan sitä.

Aloitetaan!

Miinanraivaajapelissä on kolmenlaisia solut, eli merkityt (solut, jotka sisältävät kaivoksen tai pommin), peitetyt solut, jotka ovat napsautettavia, paljastamattomat solut, jotka ovat jo alttiina.

Aluksi voimme napsauttaa mitä tahansa satunnaista solua, ja jos valitettavasti se on kaivos, pelisi on ohi. Jos napsautetussa solussa on numero, se tarkoittaa, että tällä solulla on korkeintaan nämä monet ympäröivät miinat.

Solun mahdolliset naapurit

Solulle on kahdeksan naapuria

Solu ruudukon kohdassa (x, y) ja ympäröivät naapurit

Otetaan esimerkki solusta, jolla on numero se.

Keskussolussa on numero 1, mikä tarkoittaa, että siinä on vähintään ja enintään yksi kaivos ympäröivissä naapureissa.
Tämä voi olla mahdollinen minun sijainti ja se edustaa mahdollista oikeaa ruudukkoa
Koska solussa on 1, se tarkoittaa, että on vain yksi mi sen vieressä, mutta tässä näytetään kaksi miinaa. Joten tämä ei ole mahdollista. Tämä on väärä ruudukko.

Vastaavasti esimerkki kahdesta solusta, joissa on numero.

Tämä on kelvollinen. Molemmissa soluissa voi olla vain yksi ympäröivä kaivos ja tämä kaivos on molempien kaivosten vieressä.
Tämä on virheellinen. Molemmilla soluilla voi olla vain yksi ympäröivä kaivos, mutta tässä molemmissa soluissa on kaksi vierekkäistä miinaa naapureissa.

Luulen, että olet ehkä ymmärtänyt logiikan miinanraivaajapelin takana. Oletetaan, että sinulle annetaan yksi napsautuskohta ja sinun on tutkittava miinanraivaajapelin solut mahdollisimman paljon.

Ongelma (Lähde – Leetcode)

Sinulle annetaan 2D-matriisi, joka edustaa pelilautaa. M edustaa paljastamatonta minun, E edustaa paljastamatonta tyhjä ruutu, B edustaa paljasti tyhjän neliön, jossa ei ole vierekkäisiä (ylhäällä, alla, vasemmalla, oikealla ja kaikilla 4 lävistäjällä) miinoja, numero (1 – 8) edustaa kuinka monta miinaa tämän paljastaman neliö ja lopuksi X edustaa paljasti minun.

Nyt annetaan seuraava napsautuskohta (rivi- ja sarakeindeksit) kaikkien paljastamaton neliöt (M tai E), palauta lauta paljastettuasi tämän sijainnin seuraavien sääntöjen mukaisesti:

Jos miini (M) paljastetaan, peli on ohi muuta se muotoon X .

Jos tyhjä neliö (E) yhtään vierekkäistä kaivosta ei paljasteta, vaihda sitten paljastettuun aihioon (B) ja kaikkiin sen viereisiin paljastamattomat -neliöt tulee paljastaa rekursiivisesti.

Jos tyhjä neliö (E), jossa ainakin yksi vierekkäinen kaivos paljastetaan, vaihda se sitten viereisten miinojen lukumäärää edustavaksi numeroksi (1 – 8).

Palauta lauta, kun enempää neliöitä ei tule näkyviin.

Syvyyden ensimmäinen haku – itsestään selittävä koodi

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

Toiminto päivittää kortti napsautuksen jälkeen

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

Monimutkaisuusanalyysi

Ajan monimutkaisuus: O (m * n) pahimmassa tapauksessa, missä m on rivien lukumäärä ja n on sarakkeiden lukumäärä.Suoritamme DFS: ää ruudukossa napsautusasemasta

Avaruuden monimutkaisuus: O (m * n ) pinotilaa rekursioon

Kaverit Toivon todella, että pidät tätä artikkelia arvokkaana! Jos sinulla on kysyttävää, voit varmasti keskustella niistä alla olevassa kommenttiosassa.

Kiitos paljon aikaa omistautumisesta tähän blogiin.