Minesweeper

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
2 upvotes
Asked in companies
UberThought Works

Problem statement 

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.
Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2
5 5
. . 1 _ _
. . 2 1 _
. . . 1 _
1 . . 2 _
. . # 1 _
0 1
4 6
. . # 1 . .
2 3 . . . .
_ 1 . . 4 .
_ 1 . . . .
0 2

Sample Output 1:

_ _ 1 _ _
_ _ 2 1 _
_ _ _ 1 _
1 1 1 2 _
. . # 1 _
. . * 1 . .
2 3 . . . .
_ 1 . . 4 .
_ 1 . . . .

Explanation of Sample Output 1:

Test Case 1 :
The configuration of ‘gameBoard’ is:
. . * 1 . .
2 3 . . . .
_ 1 . . 4 .
_ 1 . . . .
And, the click position is (0, 1).
At (0, 1), we have an unrevealed cell. So, we will count the number of neighbouring mines, which is 0. So, we will replace the ‘.’ by ‘_’ and then recur in all eight directions from (0, 1). The possible click positions will then be (0, 0), (0, 2), (1, 0), (1, 1), (1, 2).
After recurring for all click positions, the final configuration of the board will be:
_ _ 1 _ _
_ _ 2 1 _
_ _ _ 1 _
1 1 1 2 _
. . # 1 _
which will be printed as output.


Test Case 2 : 
The configuration of ‘gameBoard’ is:
. . # 1 . .
2 3 . . . .
_ 1 . . 4 .
_ 1 . . . .
And, click position is (0, 2).
We can see that the cell at (0, 2) contains an unrevealed mine (‘#’). So, according to the rules, we will replace the unrevealed mine (‘#’) by a revealed mine (‘*’) and return the board.
Therefore, the final configuration of the board will be:
. . * 1 . .
2 3 . . . .
_ 1 . . 4 .
_ 1 . . . .
which will be printed as output.

Sample Input 2:

1
4 6
. . # 1 . .
2 3 . . . .
_ 1 . . 4 .
_ 1 . . . .
3 2

Sample Output 2:

. . # 1 _ _
2 3 1 1 _ _
_ 1 _ _ 4 _
_ 1 _ _ _ _
Hint

This is a typical search problem. We can start from the click position and traverse the board as per the mentioned rules.

Approaches (2)
Depth First Search

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’.
Time Complexity

O(M * N), where ‘M’ and ‘N’ are the numbers of rows and columns of the matrix, respectively.

 

In the worst case, we will traverse in each cell, which is equivalent to traversing the complete matrix.

Space Complexity

O(M * N), where ‘M’ and ‘N’ are the numbers of rows and columns of the matrix, respectively.

 

Our ‘revealAndUpdate’ function requires O(M * N) space in the form of recursive stack space.

Code Solution
(100% EXP penalty)
Minesweeper
Full screen
Console