Last Updated: 27 Mar, 2021

Minesweeper

Moderate

Asked in companies

Solve now

Problem statement

Minesweeper is a popular computer game of the 1980s. Similar to that, you are given a 2D char matrix representing the game board as:

1) ‘#’ (HASH) represents an unrevealed mine.
2) ‘.’ (DOT) represents an unrevealed empty cell.
3) ‘_’ (UNDERSCORE) represents a revealed blank cell that has no neighbouring mines.
4) Digits (‘1’ to ‘8’) represents the number of neighbouring mines corresponding to the current cell.
5) ‘*’ (ASTERISK) represents a revealed mine.

In this game, you are given a click position (row & column indices) among all unrevealed cells (‘#’ or ‘.’). Your task is to return the game board after revealing the click position as per the following rules:

1) If the revealed cell contains a mine (‘#’), then the game is over - change it to ‘*’.
2) If the revealed cell is empty ('.') with no neighbouring mines revealed, then change it to revealed blank ('_'), and all of its neighbouring unrevealed cells should be revealed recursively.
3) If the revealed cell is empty ('.') with at least one neighbouring mine revealed, then change it to a digit ('1' to '8') representing the number of neighbouring mines.

Note:

1) Two cells are neighbours if they share a corner or an edge, i.e., cells corresponding above, below, left, right, and all four diagonals.
2) For simplicity, ignore the rules which are not mentioned in this problem. For example, when the game is over,  you don't need to reveal all the unrevealed mines.

Input Format:

The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains two single-spaced integers, ‘M’ and ‘N’, representing the number of rows and columns of the matrix, respectively.

The next ‘M’ line contains ‘N’ single-spaced elements.

The last line of each test case contains two single-spaced integers, ‘x’ and ‘y’, representing the row and column indices of the click position, respectively.

Output Format:

For each test case, return the updated game board when no more cells can be revealed.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= M, N <= 50
0 <= x <= M - 1
0 <= y <= N - 1
data ∈ {‘#’, ‘*’, ‘.’, ‘_’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’}

Where ‘data’ is the value of the elements of the matrix, "gameBoard".

The click position will correspond to an unrevealed cell ('#' or '.'), which also means the input board contains at least one clickable cell.
The input board is not provided at a stage when the game is over (some mines have been revealed).

Time Limit: 1 sec

Solve now

Approaches

01 Approach

The idea is to use the DFS algorithm to perform the traversal on the board.

As defined in the rules, if the click position represents a mine ‘#’, we will mark it ‘*’ and stop the traversal. Otherwise, if the click position represents an empty cell, then we will traverse according to neighboring mines.

So, if the current cell (i.e., click position) is surrounded by neighboring mines, we will update the current cell by the number of neighboring mines. If not, then the current cell will be updated by ‘_’, and we will continue our search for its eight neighboring cells.

Algorithm:

If GAMEBOARD[x][y] == ‘#’ that shows that the click position is a mine. So, update the cell by ‘*’ and return ‘GAMEBOARD’.
Else call ‘revealAndUpdate’ function that will perform DFS according to mentioned rules.
Return the ‘GAMEBOARD’.

Description of ‘revealAndUpdate’ function

This function will take five parameters :

‘GAMEBOARD’: A 2D matrix that represents the board.
‘M’: An integer variable that represents the number of rows of the board.
‘N’: An integer variable that represents the number of columns of the board.
‘X’: An integer variable that stores the row-index of click position.
‘Y’: An integer variable that stores the column-index of click position.

void revealAndUpdate('GAMEBOARD', ‘M’, ‘N’, ‘X’, ‘Y’):

If ‘X’ < 0 or ‘Y’ < 0 or ‘X’ >= 'M' or ‘Y’ >= 'N' or 'GAMEBOARD[X][Y]' != ‘.’ that shows that either the click position is not valid or the current cell is not an unrevealed empty cell. So, return back to the caller function.
Otherwise, the current cell is an unrevealed empty cell. So, call the ‘countNeighbouringMines’ function and store the returned value as an integer variable, ‘neighbouringMines’. The ‘countNeighbouringMines’ function counts the number of neighboring mines surrounding the current cell.
If ‘NEIGHBOURINGMINES’ == 0, that shows that the current cell does not have any neighboring mines. So, update the current cell by ‘_’ and recursively call the ‘revealAndUpdate’ function for all neighboring cells in all eight directions.
Else, the current cell is surrounded by ‘NEIGHBOURINGMINES’ number of mines. So, update the current cell by ‘neighbouringMines’.

Description of ‘countNeighbouringMines’ function

This function will take five parameters :

‘GAMEBOARD’: A 2D matrix that represents the board.
‘M’: An integer variable that represents the number of rows of the board.
‘N’: An integer variable that represents the number of columns of the board..
‘X’: An integer variable that stores the row-index of click position.
‘Y’: An integer variable that stores the column-index of click position.

void countNeighbouringMines(GAMEBOARD, ‘M’, ‘N’, ‘X’, ‘Y’):

Declare an integer variable ‘COUNT’ that will store the number of mines surrounding the given cell, represented by the click position.
Run a loop from ‘ROW’ = ‘X’ - 1 till ‘ROW’ = ‘X’ + 1
- Run a loop from ‘COL’ = ‘Y’ - 1 till ‘COL’ = ‘Y’ + 1
  - If (('ROW' == ‘X’ && ‘COL’ == ‘Y’) || ‘ROW’ < 0 || ‘COL’ < 0 || ‘ROW’ >= ‘M’ || ‘COL’ >= ‘N’) that shows that indices, ‘ROW’ and ‘COL’ are not valid so skip the below steps.
  - Otherwise, check if GAMEBOARD[ROW][COL] == ‘#’ that shows it is a mine. So, increment the count by 1.
Return ‘COUNT’.

Solve now

02 Approach

The idea is to use the BFS algorithm for traversing and updating the board.

First, we will check whether the cell at the given click position is mine or not. If yes, then we will return the board after updating the cell at click position by ‘*’. Otherwise, we will perform the BFS on the given board using a queue and update the cells as per the mentioned rules.

Algorithm:

If ‘GAMEBOARD[X][Y]’ == ‘#’ that shows that the click position is mine. So, update the cell by ‘*’ and return ‘GAMEBOARD’.
Declare a queue of the pair of int, ‘Q’ and push indices of click position, i.e., {X, Y} in the ‘Q.
Run a loop while ‘Q is not empty.
- Extract the indices at the front of ‘Q in integer variables, ‘X’ and ‘Y’. Then, pop the front element from the ‘Q.
- Now declare an integer variable, ’NEIGHBOURINGMINES’ that will store the count of all neighboring mines surrounding the cell having row and column indices as ‘X’ and ‘Y’, respectively.
- Run a loop from ‘ROW’ = ‘X’ - 1 till ‘ROW’ = ‘X’ + 1
  - Run a loop from ‘COL’ = ‘Y’ - 1 till ‘COL’ = ‘Y’ + 1
    - If (('ROW' == ‘X’ && ‘COL’ == ‘Y’) || ‘ROW’ < 0 || ‘COL’ < 0 || ‘ROW’ >= ‘M’ || ‘COL’ >= ‘N’) that shows that indices, ‘ROW’ and ‘COL’ are not valid so skip the below steps.
    - Otherwise, check if ‘GAMEBOARD[ROW][COL]’ == ‘#’ that shows it is a mine. So, increment the ’NEIGHBOURINGMINES’ by 1.
- If ‘NEIGHBOURINGMINES’ == 0, that shows that the current cell does not have any neighboring mines. So, update the current cell by ‘_’.
  - Run a loop from ‘ROW’ = ‘X’ - 1 till ‘ROW’ = ‘X’ + 1
    - Run a loop from ‘COL' = ‘Y’ - 1 till ‘COL’ = ‘Y’ + 1
      - If ((‘ROW’ == ‘X’ && ‘COL’ == ‘Y’) || ‘ROW’ < 0 || ‘COL’ < 0 || ‘ROW’ >= ‘M’ || ‘COL’ >= ‘N’) that shows that indices, ‘ROW’ and ‘COL’ are not valid so skip the below steps.
      - Otherwise, check if ‘GAMEBOARD[ROW][COL]’ == ‘.’ that shows it is an unrevealed empty cell. So, push the ‘ROW’ and ‘COL’ in the ‘Q and update the cell by ‘_’.
- Else, the current cell is surrounded by a ‘NEIGHBOURINGMINES’ number of mines. So, update the current cell by ‘NEIGHBOURINGMINES’.
Return the ‘GAMEBOARD’.

Solve now