529. Minesweeper


Problem Description

The Minesweeper game consists of a board with mines ('M') and empty squares ('E'). The objective is to reveal all squares without triggering a mine. When a player clicks a square:

  1. If a mine is revealed ('M'), the game ends and the mine becomes an 'X'.
  2. If an empty square ('E') without adjacent mines is revealed, it becomes a 'B', representing a blank space, and its adjacent unrevealed squares should also be revealed recursively.
  3. If an empty square ('E') with adjacent mines is revealed, it shows a digit ('1' to '8') representing the number of mines in the adjacent squares.
  4. The board state is returned when no more squares can be revealed.

The task is to implement the logic that simulates this part of Minesweeper game behavior.

Intuition

To solve this problem, we use Depth-First Search (DFS) algorithm, where we start from the clicked position and explore adjacent squares. Here's a step-by-step breakdown:

  1. Check the square at the clicked position:

    • If it's a mine ('M'), change it to an 'X'.
    • If it's an empty square ('E'), perform the following:
      • Count the number of mines in the adjacent squares.
      • If there are adjacent mines, update the square with the mine count.
      • If there are no adjacent mines, update the square to a 'B' and recursively reveal adjacent 'E' squares.
  2. The base case for recursive DFS is when the current square is not an 'E' or when it is out of bounds, in which case we just return.

  3. By following the steps above, we ensure that we reveal only the necessary squares to either show the number of adjacent mines or to expand the empty regions ('E' to 'B').

  4. The recursion naturally takes care of revealing all connected empty squares ('E' to 'B') and stopping when it encounters numbered squares or the edge of the board.

This DFS approach encapsulates the essence of Minesweeper's revealing mechanic, carefully unveiling the board according to the game's rules.

Learn more about Depth-First Search and Breadth-First Search patterns.

Solution Approach

The implementation of the solution is a straightforward application of Depth-First Search (DFS). Here are the details of the implementation steps, corresponding to the given Python code:

  1. The nested dfs function is defined to perform a DFS starting from a particular cell on the board.

  2. The main logic for the DFS method is as follows:

    • First, we count the number of mines ('M') around the current square (i, j). This is done in a nested loop where we iterate over all adjacent cells including diagonals.
    • If there is at least one mine adjacent to (i, j), we update the current square with the number of mines (cnt).
    • If there are no adjacent mines, we update the current square to 'B'. We then recursively call dfs on all adjacent unrevealed squares ('E') to continue revealing the board.
  3. Before DFS is initiated, we first check the cell at the click coordinates. If the clicked cell is a mine ('M'), we update it to 'X' to indicate the game is over. Otherwise, we call our dfs function with the click coordinates.

  4. The dfs function is designed to stop the recursive calls when it encounters a cell that is not 'E', which handles both the case when revealing 'B' squares, stopping at the border, and stopping at numbered squares.

  5. The dfs function also ensures that we never go out of bounds of the board by checking whether the coordinates (x, y) are within the range [0, m) for rows and [0, n) for columns, where m and n are the lengths of the board's rows and columns respectively.

  6. The updateBoard function then returns the updated board once all the possible and necessary cells are revealed based on the initial click.

This implementation ensures that all recursive calls to reveal cells only act on valid, in-bound, and appropriate cells, preventing unnecessary work and ensuring that the board state is mutated correctly according to Minesweeper rules.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Example Walkthrough

Let's go through a small example to illustrate the solution approach. Suppose we have a Minesweeper board like this, and the player clicks on the cell at row 1, column 2 (indexes are zero-based):

1[['E', 'E', 'E', 'E'],
2 ['E', 'E', 'E', 'M'],
3 ['E', 'M', 'E', 'E'],
4 ['E', 'E', 'M', 'E']]

We will follow the solution steps for our DFS approach using this board:

  1. Initialize – We note the player's click on cell (1, 2), which is 'E'.

  2. DFS Function Call – We check whether the clicked cell is 'M' or 'E'. Since it's 'E', we invoke our dfs function here.

  3. Count Mines – We look at all the adjacent cells around (1, 2). The adjacent cells contain one mine at (2, 1). Therefore, the mine count cnt is 1.

  4. Update Cell – Since there's one mine adjacent to (1, 2), we update the board as follows, replacing 'E' with '1' to indicate the number of adjacent mines:

1[['E', 'E', 'E', 'E'],
2 ['E', 'E', '1', 'M'],
3 ['E', 'M', 'E', 'E'],
4 ['E', 'E', 'M', 'E']]
  1. Adjacent Squares – Since cell (1, 2) is next to only one mine, we don't perform recursive calls on its neighbors as per standard Minesweeper rules.

  2. Final Board – The updateBoard function returns the board since we cannot reveal any further cells based on the click position.

This updated board represents the state after the single click, adhering to the rules of Minesweeper where numbered cells should not reveal their neighbors. If the initial click was on a different 'E' cell, especially one not adjacent to any mines, the recursive dfs would take effect, revealing a larger area by turning 'E' cells to 'B' and uncovering all interconnected blank spaces.

Solution Implementation

1from typing import List
2
3class Solution:
4    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
5        # The recursive function to reveal the board starting from the clicked cell.
6        def reveal(i: int, j: int):
7            # Count mines around the current cell
8            mine_count = 0
9            for x in range(max(i - 1, 0), min(i + 2, rows)):  # Limits the range on the board
10                for y in range(max(j - 1, 0), min(j + 2, columns)):  # Limits the range on the board
11                    if board[x][y] == "M":
12                        mine_count += 1
13          
14            # If there are mines around the cell, update with mine count
15            if mine_count > 0:
16                board[i][j] = str(mine_count)
17            else:
18                # Otherwise, set the cell to "B" for blank and reveal surrounding cells
19                board[i][j] = "B"
20                for x in range(max(i - 1, 0), min(i + 2, rows)):
21                    for y in range(max(j - 1, 0), min(j + 2, columns)):
22                        if board[x][y] == "E":
23                            reveal(x, y)
24
25        # Get the size of the board
26        rows, columns = len(board), len(board[0])
27      
28        # The clicked position
29        click_row, click_col = click
30      
31        # If the clicked cell contains a mine, game over
32        if board[click_row][click_col] == "M":
33            board[click_row][click_col] = "X"
34        else:
35            # Start revealing from the clicked cell
36            reveal(click_row, click_col)
37      
38        # Return the updated board
39        return board
40
1class Solution {
2    private char[][] gameBoard; // Renamed board to gameBoard for clarity
3    private int rows;           // Renamed m to rows for clarity
4    private int cols;           // Renamed n to cols for clarity
5
6    // Function updates the game board when a user clicks on a cell (i.e., uncovers the cell)
7    public char[][] updateBoard(char[][] board, int[] click) {
8        rows = board.length;        // Total number of rows in the board
9        cols = board[0].length;     // Total number of columns in the board
10        gameBoard = board;          // Assign board to gameBoard for internal use
11
12        int clickRow = click[0], clickCol = click[1]; // Row and column indexes of the click position
13
14        // Check if the clicked cell contains a mine
15        if (gameBoard[clickRow][clickCol] == 'M') {
16            gameBoard[clickRow][clickCol] = 'X'; // If there's a mine, mark the cell as 'X'
17        } else {
18            // If the clicked cell does not contain a mine, perform Depth First Search (DFS) from this cell
19            dfs(clickRow, clickCol);
20        }
21        return gameBoard; // Return the updated board
22    }
23
24    // Performs Depth First Search (DFS) to reveal cells
25    private void dfs(int row, int col) {
26        int mineCount = 0; // Counter for adjacent mines
27
28        // Iterate through the adjacent cells
29        for (int x = row - 1; x <= row + 1; ++x) {
30            for (int y = col - 1; y <= col + 1; ++y) {
31                // Check if the adjacent cell is within the board and if it contains a mine
32                if (x >= 0 && x < rows && y >= 0 && y < cols && gameBoard[x][y] == 'M') {
33                    mineCount++; // Increment the mine counter
34                }
35            }
36        }
37
38        if (mineCount > 0) { 
39            // If there are mines found around the cell, display the mine count
40            gameBoard[row][col] = (char) (mineCount + '0');
41        } else {
42            // If there are no mines around the cell, mark the cell as 'B' for blank
43            gameBoard[row][col] = 'B';
44            // Recursively reveal adjacent cells that are not mines and are unrevealed ('E')
45            for (int x = row - 1; x <= row + 1; ++x) {
46                for (int y = col - 1; y <= col + 1; ++y) {
47                    if (x >= 0 && x < rows && y >= 0 && y < cols && gameBoard[x][y] == 'E') {
48                        dfs(x, y); // Recursive call to dfs
49                    }
50                }
51            }
52        }
53    }
54}
55
1class Solution {
2public:
3    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
4        int rows = board.size(), cols = board[0].size();
5        int clickRow = click[0], clickCol = click[1];
6
7        // Using lambda function to perform Depth-First Search (DFS)
8        function<void(int, int)> dfs = [&](int row, int col) {
9            int mineCount = 0;
10
11            // Count mines in adjacent cells
12            for (int x = row - 1; x <= row + 1; ++x) {
13                for (int y = col - 1; y <= col + 1; ++y) {
14                    if (x >= 0 && x < rows && y >= 0 && y < cols && board[x][y] == 'M') {
15                        ++mineCount;
16                    }
17                }
18            }
19
20            // If mines exist around the cell, update the cell with the mine count. Otherwise, mark the cell as 'B' and continue DFS.
21            if (mineCount > 0) {
22                board[row][col] = mineCount + '0';
23            } else {
24                board[row][col] = 'B';
25                for (int x = row - 1; x <= row + 1; ++x) {
26                    for (int y = col - 1; y <= col + 1; ++y) {
27                        if (x >= 0 && x < rows && y >= 0 && y < cols && board[x][y] == 'E') {
28                            dfs(x, y);
29                        }
30                    }
31                }
32            }
33        };
34
35        // Handle the initial click
36        if (board[clickRow][clickCol] == 'M') {
37            // If the clicked cell contains a mine, game over
38            board[clickRow][clickCol] = 'X';
39        } else {
40            // If the clicked cell is empty ('E'), perform DFS to reveal cells
41            dfs(clickRow, clickCol);
42        }
43
44        return board;
45    }
46};
47
1function updateBoard(board: string[][], click: number[]): string[][] {
2    const rowCount = board.length; // Number of rows in the board
3    const colCount = board[0].length; // Number of columns in the board
4    const [rowClicked, colClicked] = click; // Destructure click into row and column indices
5
6    // Deep-First Search function to reveal the board
7    const revealBoard = (row: number, col: number) => {
8        let mineCount = 0;
9        // Count the number of mines surrounding the current cell
10        for (let x = row - 1; x <= row + 1; ++x) {
11            for (let y = col - 1; y <= col + 1; ++y) {
12                if (x >= 0 && x < rowCount && y >= 0 && y < colCount && board[x][y] === 'M') {
13                    mineCount++;
14                }
15            }
16        }
17
18        if (mineCount > 0) { // If mines are found around the cell, update the cell with the mine count
19            board[row][col] = mineCount.toString();
20        } else { // If no mines are found, mark the cell as 'B' and continue the search
21            board[row][col] = 'B';
22            for (let x = row - 1; x <= row + 1; ++x) {
23                for (let y = col - 1; y <= col + 1; ++y) {
24                    // Recursively reveal the board for surrounding cells
25                    if (x >= 0 && x < rowCount && y >= 0 && y < colCount && board[x][y] === 'E') {
26                        revealBoard(x, y);
27                    }
28                }
29            }
30        }
31    };
32
33    // Click processing
34    if (board[rowClicked][colClicked] === 'M') {
35        // If the click is on a mine, game is over. Mark the clicked mine with 'X'
36        board[rowClicked][colClicked] = 'X';
37    } else {
38        // If the click is not on a mine, reveal the board from the clicked spot
39        revealBoard(rowClicked, colClicked);
40    }
41
42    return board; // Return the updated board state
43}
44

Time and Space Complexity

The given Python code is a solution for the Minesweeper game where a player clicks on a cell on the board and depending on the board cell content, different actions may be taken.

Time Complexity:

The time complexity is determined by the number of times dfs is invoked and how many cells it inspects each time. In the worst-case scenario, dfs performs a Depth-First Search on the entire board starting from the clicked cell.

  • Each cell is visited at most once due to the fact that once a cell is visited it changes from "E" (empty) to "B" (blank) or it becomes a digit representing the number of adjacent mines.
  • For each cell visited, dfs inspects up to 8 adjacent cells.

Given a board of size m x n, the time complexity is thus O(m * n) since in the worst-case scenario, we might end up visiting each cell once.

Space Complexity:

The space complexity of this DFS solution is primarily determined by the recursion stack used by the dfs function.

  • In the worst-case scenario, the DFS could recurse to a depth where the entire board is traversed, making the maximum recursion depth m * n in a situation where all cells are empty ("E") and connected, requiring the algorithm to visit every cell before hitting a base case.

The space complexity is hence O(m * n) due to the recursion stack in the worst-case scenario.

When looking at auxiliary space (excluding space for inputs and outputs), the space complexity depends on the number of recursive calls placed on the stack, which remains O(m * n).

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer techniques do you use to check if a string is a palindrome?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄