# Minesweeper
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minesweeper)
Canonical: https://scaleengineer.com/dsa/problems/minesweeper
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Matrix
**Companies:** [Anduril](https://scaleengineer.com/companies/anduril), [Applied Intuition](https://scaleengineer.com/companies/applied-intuition), [Robinhood](https://scaleengineer.com/companies/robinhood), [Yext](https://scaleengineer.com/companies/yext)
---
## Problem
Let's play the minesweeper game ([Wikipedia](https://en.wikipedia.org/wiki/Minesweeper%5F%28video%5Fgame%29), [online game](http://minesweeperonline.com))!

You are given an `m x n` char matrix `board` representing the game board where:

* `'M'` represents an unrevealed mine,
* `'E'` represents an unrevealed empty square,
* `'B'` represents a revealed blank square that has no adjacent mines (i.e., above, below, left, right, and all 4 diagonals),
* digit (`'1'` to `'8'`) represents how many mines are adjacent to this revealed square, and
* `'X'` represents a revealed mine.

You are also given an integer array `click` where `click = [clickr, clickc]` represents the next click position among all the unrevealed squares (`'M'` or `'E'`).

Return _the board after revealing this position according to the following rules_:

1. If a mine `'M'` is revealed, then the game is over. You should change it to `'X'`.
2. If an empty square `'E'` with no adjacent mines is revealed, then change it to a revealed blank `'B'` and all of its adjacent unrevealed squares should be revealed recursively.
3. If an empty square `'E'` with at least one adjacent mine is revealed, then change it to a digit (`'1'` to `'8'`) representing the number of adjacent mines.
4. Return the board when no more squares will be revealed.

**Example 1:**

![](https://assets.glich.co/dsa/minesweeper/image0.jpeg) 

**Input:** board = [["E","E","E","E","E"],["E","E","M","E","E"],["E","E","E","E","E"],["E","E","E","E","E"]], click = [3,0]
**Output:** [["B","1","E","1","B"],["B","1","M","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]]

**Example 2:**

![](https://assets.glich.co/dsa/minesweeper/image1.jpeg) 

**Input:** board = [["B","1","E","1","B"],["B","1","M","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]], click = [1,2]
**Output:** [["B","1","E","1","B"],["B","1","X","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]]

**Constraints:**

* `m == board.length`
* `n == board[i].length`
* `1 <= m, n <= 50`
* `board[i][j]` is either `'M'`, `'E'`, `'B'`, or a digit from `'1'` to `'8'`.
* `click.length == 2`
* `0 <= clickr < m`
* `0 <= clickc < n`
* `board[clickr][clickc]` is either `'M'` or `'E'`.

# Approaches
## Brute Force with Repeated Board Scans
This approach simulates the cascading reveal by repeatedly scanning the entire board. After the initial click is processed, if it results in a blank square ('B'), we enter a loop. In each iteration of the loop, we scan every cell of the board. If we find an unrevealed empty square ('E') that is adjacent to a revealed blank square ('B'), we reveal it. We repeat this process until a full scan of the board results in no new squares being revealed.
**Time:** O((M*N)^2). In the worst-case scenario, we might only reveal one 'E' cell per full board scan. A full scan takes O(M*N) time. If a large portion of the board needs to be revealed, the number of passes could be proportional to M*N, leading to a quadratic time complexity. · **Space:** O(1) extra space. The board is modified in-place, and only a constant number of variables are used for control flow.
**Pros:** Simple to conceptualize.; Very low space complexity as it only uses a few extra variables.
**Cons:** Highly inefficient in terms of time complexity due to repeated scanning of the entire board.; The logic is more complex to implement correctly compared to traversal-based approaches, especially managing the loop condition and state changes.
### Explanation
The brute-force method tackles the problem by iteratively refining the board's state. After handling the first click, if a cascading reveal is triggered (the clicked cell becomes 'B'), the algorithm enters a state of continuous scanning. It repeatedly sweeps through the entire grid, cell by cell. In each sweep, it looks for unrevealed empty squares ('E') that are next to already revealed blank squares ('B'). When such a square is found, it's revealed according to the game's rules. This entire process of sweeping continues until a full pass over the board yields no new revealed squares, at which point the board is considered stable and is returned.

```java
class Solution {
    public char[][] updateBoard(char[][] board, int[] click) {
        int r = click[0], c = click[1];
        int m = board.length, n = board[0].length;

        if (board[r][c] == 'M') {
            board[r][c] = 'X';
            return board;
        }

        int mines = countAdjacentMines(board, r, c, m, n);
        if (mines > 0) {
            board[r][c] = (char) (mines + '0');
            return board;
        }
        
        board[r][c] = 'B';

        boolean changedInPass = true;
        while (changedInPass) {
            changedInPass = false;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == 'E' && hasAdjacentBlank(board, i, j, m, n)) {
                        int adjacentMines = countAdjacentMines(board, i, j, m, n);
                        if (adjacentMines > 0) {
                            board[i][j] = (char) (adjacentMines + '0');
                        } else {
                            board[i][j] = 'B';
                        }
                        changedInPass = true;
                    }
                }
            }
        }
        return board;
    }

    private int countAdjacentMines(char[][] board, int r, int c, int m, int n) {
        int count = 0;
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                if (i == 0 && j == 0) continue;
                int nr = r + i;
                int nc = c + j;
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && board[nr][nc] == 'M') {
                    count++;
                }
            }
        }
        return count;
    }

    private boolean hasAdjacentBlank(char[][] board, int r, int c, int m, int n) {
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                if (i == 0 && j == 0) continue;
                int nr = r + i;
                int nc = c + j;
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && board[nr][nc] == 'B') {
                    return true;
                }
            }
        }
        return false;
    }
}
```
### Algorithm
- Handle the initial click at `(r, c)`. If it's a mine ('M'), change it to 'X' and return.
- If it's an empty square ('E'), count its adjacent mines. If the count is positive, update the square to the digit and return. Otherwise, update it to 'B'.
- If the initial click resulted in a 'B', start a loop that continues as long as changes are made to the board in a single pass. A boolean flag, `changedInPass`, can track this.
- Inside the loop, iterate through every cell `(i, j)` of the board.
- For each cell, if it's an 'E', check if it has any adjacent 'B' cells.
- If it does, reveal the cell `(i, j)` by counting its adjacent mines and updating it to a digit or 'B'. If the cell is updated, set `changedInPass` to `true`.
- If the loop completes a full pass without any changes (`changedInPass` remains `false`), exit the loop and return the board.

## Breadth-First Search (BFS)
A much more efficient approach is to treat the board as a graph and perform a traversal. When an empty square ('E') with no adjacent mines is clicked, it's changed to a blank square ('B'), and we start a Breadth-First Search (BFS) from this square. BFS is ideal for finding the shortest path or, in this case, exploring layer by layer, which naturally mimics the cascading reveal of Minesweeper. We use a queue to keep track of the 'B' squares whose neighbors we need to reveal.
**Time:** O(M*N). In the worst case, BFS will visit every cell on the board once. For each cell, we perform a constant amount of work (checking 8 neighbors). Thus, the total time is proportional to the number of cells. · **Space:** O(M*N). The space is dominated by the queue. In the worst case, the queue could hold a number of elements proportional to the size of the board (e.g., a checkerboard pattern of 'E's).
**Pros:** Optimal time complexity, as each cell is processed at most once.; It's a systematic way to explore the grid, which avoids redundant computations.
**Cons:** The space complexity can be significant in the worst case, where the queue might need to hold a large number of cells.
### Explanation
This approach correctly models the problem as a graph traversal. The process begins with the initial click. If a mine is hit, the game ends. Otherwise, the clicked 'E' square is evaluated. If it has adjacent mines, it's updated with a number, and the process stops. If it has no adjacent mines, it becomes a 'B', and a BFS is initiated from this cell. The BFS uses a queue to manage the cells to visit. It systematically explores neighbors, revealing them based on the rules. An 'E' cell adjacent to the current 'B' cell is revealed as a number if it has neighboring mines, or as another 'B' if it doesn't. New 'B' cells are added to the queue to continue the expansion. This ensures that every cell in a connected component of empty squares is visited and revealed exactly once.

```java
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public char[][] updateBoard(char[][] board, int[] click) {
        int m = board.length, n = board[0].length;
        int r = click[0], c = click[1];

        if (board[r][c] == 'M') {
            board[r][c] = 'X';
            return board;
        }

        int[] dr = {-1, -1, -1, 0, 0, 1, 1, 1};
        int[] dc = {-1, 0, 1, -1, 1, -1, 0, 1};

        int mines = 0;
        for (int i = 0; i < 8; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && board[nr][nc] == 'M') {
                mines++;
            }
        }

        if (mines > 0) {
            board[r][c] = (char) (mines + '0');
            return board;
        }

        board[r][c] = 'B';
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{r, c});

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int curr_r = cell[0];
            int curr_c = cell[1];

            for (int i = 0; i < 8; i++) {
                int nr = curr_r + dr[i];
                int nc = curr_c + dc[i];

                if (nr >= 0 && nr < m && nc >= 0 && nc < n && board[nr][nc] == 'E') {
                    int neighborMines = 0;
                    for (int j = 0; j < 8; j++) {
                        int nnr = nr + dr[j];
                        int nnc = nc + dc[j];
                        if (nnr >= 0 && nnc < m && nnc >= 0 && nnc < n && board[nnr][nnc] == 'M') {
                            neighborMines++;
                        }
                    }

                    if (neighborMines > 0) {
                        board[nr][nc] = (char) (neighborMines + '0');
                    } else {
                        board[nr][nc] = 'B';
                        queue.offer(new int[]{nr, nc});
                    }
                }
            }
        }
        return board;
    }
}
```
### Algorithm
- Handle the initial click at `(r, c)`. If it's a mine ('M'), change it to 'X' and return.
- Count the number of mines adjacent to `(r, c)`.
- If the mine count is greater than 0, update `board[r][c]` to the digit representing the count and return.
- If the mine count is 0, update `board[r][c]` to 'B'. This cell is the starting point for the BFS.
- Initialize a queue and add the coordinates `(r, c)` to it.
- While the queue is not empty:
  - Dequeue a cell `(curr_r, curr_c)`.
  - Iterate through its 8 neighbors `(nr, nc)`.
  - For each neighbor that is within bounds and is an unrevealed empty square ('E'):
    - Count the mines adjacent to this neighbor `(nr, nc)`.
    - If the count is positive, update the neighbor cell `board[nr][nc]` to the digit.
    - If the count is zero, update the neighbor cell `board[nr][nc]` to 'B' and enqueue it for future processing.

## Depth-First Search (DFS)
Similar to BFS, this approach uses a graph traversal algorithm, but this time it's Depth-First Search (DFS). DFS explores as far as possible along each branch before backtracking. It can be implemented elegantly using recursion. When an empty square ('E') with no adjacent mines is revealed, we change it to 'B' and then make recursive calls for all its unrevealed neighbors.
**Time:** O(M*N). Similar to BFS, each cell is visited at most once. The work done at each cell is constant (checking 8 neighbors). · **Space:** O(M*N). The space is used by the recursion call stack. In the worst case, the recursion depth can be up to M*N if the 'E' cells form a long, winding path through the grid.
**Pros:** Optimal time complexity, same as BFS.; Often leads to more concise and readable code for traversal problems due to the nature of recursion.
**Cons:** Can lead to a stack overflow error for very large grids or deep recursion paths, although this is not an issue with the given constraints (M, N <= 50).; The space complexity in the worst case can be proportional to the number of cells.
### Explanation
DFS provides an alternative, yet equally efficient, way to traverse the grid. The logic is typically implemented with a recursive function. The process starts with the clicked cell. If it's a mine, it's revealed as 'X'. If it's an 'E', a recursive DFS function is called. This function first checks for base cases: if the cell is out of bounds or already revealed, it returns. Otherwise, it counts adjacent mines. If there are any, the cell is updated to a number, and the recursion for that path terminates. If there are no adjacent mines, the cell becomes 'B', and the function then calls itself for all 8 adjacent unrevealed 'E' squares. Marking the cell as 'B' or a number before the recursive calls is key to preventing infinite loops and redundant work.

```java
class Solution {
    public char[][] updateBoard(char[][] board, int[] click) {
        int r = click[0], c = click[1];

        if (board[r][c] == 'M') {
            board[r][c] = 'X';
            return board;
        }
        
        dfs(board, r, c);
        return board;
    }

    private void dfs(char[][] board, int r, int c) {
        int m = board.length, n = board[0].length;
        if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != 'E') {
            return;
        }

        int[] dr = {-1, -1, -1, 0, 0, 1, 1, 1};
        int[] dc = {-1, 0, 1, -1, 1, -1, 0, 1};

        int mines = 0;
        for (int i = 0; i < 8; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && board[nr][nc] == 'M') {
                mines++;
            }
        }

        if (mines > 0) {
            board[r][c] = (char) (mines + '0');
        } else {
            board[r][c] = 'B';
            for (int i = 0; i < 8; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                dfs(board, nr, nc);
            }
        }
    }
}
```
### Algorithm
- The main function handles the initial click. If it's a mine ('M'), update to 'X' and return. Otherwise, call a recursive `dfs` helper function.
- The `dfs(board, r, c)` function is defined as follows:
  - **Base Case:** If the coordinates `(r, c)` are out of bounds or the cell `board[r][c]` is not 'E', return immediately. This prevents re-processing visited cells.
  - **Process Cell:** Count the mines adjacent to `(r, c)`.
  - **Update Cell & Recurse:**
    - If `mineCount > 0`, update `board[r][c]` to the digit and return. This stops the exploration along the current path.
    - If `mineCount == 0`, update `board[r][c]` to 'B'. Then, for each of the 8 neighbors, make a recursive call `dfs(board, neighbor_r, neighbor_c)`.

# Solutions
### Java

```java
class Solution {
private
  char[][] board;
private
  int m;
private
  int n;
public
  char[][] updateBoard(char[][] board, int[] click) {
    m = board.length;
    n = board[0].length;
    this.board = board;
    int i = click[0], j = click[1];
    if (board[i][j] == 'M') {
      board[i][j] = 'X';
    } else {
      dfs(i, j);
    }
    return board;
  }
private
  void dfs(int i, int j) {
    int cnt = 0;
    for (int x = i - 1; x <= i + 1; ++x) {
      for (int y = j - 1; y <= j + 1; ++y) {
        if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M') {
          ++cnt;
        }
      }
    }
    if (cnt > 0) {
      board[i][j] = (char)(cnt + '0');
    } else {
      board[i][j] = 'B';
      for (int x = i - 1; x <= i + 1; ++x) {
        for (int y = j - 1; y <= j + 1; ++y) {
          if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E') {
            dfs(x, y);
          }
        }
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<vector<char>> updateBoard(vector<vector<char>> &board,
                                   vector<int> &click) {
    int m = board.size(), n = board[0].size();
    int i = click[0], j = click[1];
    function<void(int, int)> dfs = [&](int i, int j) {
      int cnt = 0;
      for (int x = i - 1; x <= i + 1; ++x) {
        for (int y = j - 1; y <= j + 1; ++y) {
          if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M') {
            ++cnt;
          }
        }
      }
      if (cnt) {
        board[i][j] = cnt + '0';
      } else {
        board[i][j] = 'B';
        for (int x = i - 1; x <= i + 1; ++x) {
          for (int y = j - 1; y <= j + 1; ++y) {
            if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E') {
              dfs(x, y);
            }
          }
        }
      }
    };
    if (board[i][j] == 'M') {
      board[i][j] = 'X';
    } else {
      dfs(i, j);
    }
    return board;
  }
};

```

### Python

```python
class Solution:
    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]: def dfs(i: int, j: int): cnt = 0 for x in range(i - 1, i + 2): for y in range(j - 1, j + 2): if 0 <= x < m and 0 <= y < n and board[x][y] == "M": cnt += 1 if cnt: board[i][j] = str(cnt) else: board[i][j] = "B" for x in range(i - 1, i + 2): for y in range(j - 1, j + 2): if 0 <= x < m and 0 <= y < n and board[x][y] == "E": dfs(x, y) m, n = len(board), len(board[0]) i, j = click if board[i][j] == "M": board[i][j] = "X" else: dfs(i, j) return board

```