Minesweeper

(25 dec.2020)

Ați mai jucat minesweeper? Ei bine, cred că da, toată lumea a jucat acel joc în copilăria noastră. Dar nu toată lumea știe logica din spatele acestui joc minunat. Rămâneți cu mine pentru această postare și credeți-mă că o să vă fie mai simplă și o să vă placă.

Să începem!

În jocul Minesweeper, există trei tipuri de celule, adică semnalizate (celulele care conțin mine sau bombă), celule acoperite care pot fi făcute clic, celule descoperite care sunt deja expuse.

La început, putem face clic pe orice celulă aleatorie și, din păcate, este o mină, jocul tău s-a terminat. Dacă celula pe care se face clic are un număr, aceasta indică faptul că această celulă are cel mult aceste numeroase mine care o înconjoară.

Posibili vecini ai unei celule

Există opt vecini pentru o celulă

Celulă în poziția (x, y) din grilă și vecinii din jur

Să luăm un exemplu de celulă care are un număr pe it.

Celula centrală are numărul 1 pe ea, ceea ce înseamnă că are cel puțin și cel mult o mină în vecinii din jur.
Aceasta poate fi o posibilă poziție a minei și reprezintă o posibilă grilă corectă
Deoarece celula are 1 pe ea, asta înseamnă că există doar o mi ne adiacent, dar aici sunt prezentate două mine. Deci, acest lucru nu este posibil. Aceasta este o grilă incorectă.

În mod similar, exemplu de două celule având un număr pe ele.

Acest lucru este valid. Ambele celule pot avea doar o mină înconjurătoare, iar această mină este adiacentă ambelor mine.
Acest lucru este nevalid. Ambele celule pot avea doar o mină înconjurătoare, dar aici ambele celule au două mine adiacente în vecini.

Acum, cred că ați fi înțeles logica în spatele jocului de măturători. Să presupunem că vi se acordă o poziție cu un singur clic și trebuie să explorați cât mai mult posibil celulele jocului minesweeper.

Declarație de problemă (Sursă – Leetcode)

Vi se oferă o matrice de caractere 2D care reprezintă tabloul de joc. M reprezintă un nedivulgat a mea, E reprezintă un nedivulgat pătrat gol, B reprezintă un a dezvăluit pătrat gol care nu are mine adiacente (deasupra, dedesubt, stânga, dreapta și toate cele 4 diagonale), cifră (de la 1 la 8) reprezintă câte mine sunt adiacente la acest dezvăluit pătrat și, în final, X reprezintă un a dezvăluit a mea.

Acum a fost dată următoarea poziție de clic (indicii de rând și de coloană) dintre toți nerealizat pătrate („M” sau „E”), returnează tabla după ce dezvăluie această poziție conform următoarelor reguli:

Dacă o mină („M”) este dezvăluită, atunci jocul s-a terminat – schimbați-l în X .

Dacă un pătrat gol (E) cu nu se descoperă mine adiacente , apoi schimbați-l în gol dezvăluit (B) și toate unrevealed pătratele ar trebui să fie revelate recursiv.

Dacă un pătrat gol (E) cu cel puțin o mină adiacentă este dezvăluită, apoi schimbați-o cu o cifră („1” la „8”) reprezentând numărul de mine adiacente.

Întoarceți placa atunci când nu vor mai fi dezvăluite pătrate.

Căutarea în primul rând a adâncimii – cod auto-explicativ

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

Funcție de actualizare a plăcii după clic

//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 complexității

Complexitate temporală: O (m * n) în cel mai rău caz, unde m este numărul de rânduri și n este numărul de coloane.Efectuăm DFS pe grilă din poziția de clic

Complexitate spațială: O (m * n ) stivați spațiu pentru recursivitate

Băieți, sper cu adevărat că veți găsi acest articol valoros! Dacă totuși aveți întrebări, le puteți discuta cu siguranță în secțiunea de comentarii de mai jos.

Vă mulțumim mult pentru că v-ați dedicat timpul acestui blog.