Code Implementation

class Solution:
    def updateBoard(self, board, click):
        from collections import deque

        m, n = len(board), len(board[0])
        dirs = [(-1, -1), (-1, 0), (-1, 1),
                (0, -1),          (0, 1),
                (1, -1),  (1, 0), (1, 1)]

        def count_mines(x, y):
            count = 0
            for dx, dy in dirs:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and board[nx][ny] == 'M':
                    count += 1
            return count

        x, y = click
        if board[x][y] == 'M':
            board[x][y] = 'X'
            return board

        queue = deque()
        queue.append((x, y))
        while queue:
            cx, cy = queue.popleft()
            if board[cx][cy] != 'E':
                continue
            mines = count_mines(cx, cy)
            if mines == 0:
                board[cx][cy] = 'B'
                for dx, dy in dirs:
                    nx, ny = cx + dx, cy + dy
                    if 0 <= nx < m and 0 <= ny < n and board[nx][ny] == 'E':
                        queue.append((nx, ny))
            else:
                board[cx][cy] = str(mines)
        return board
      

class Solution {
public:
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        int m = board.size(), n = board[0].size();
        vector<pair<int, int>> dirs = {{-1, -1}, {-1, 0}, {-1, 1},
                                         {0, -1},           {0, 1},
                                         {1, -1},  {1, 0},  {1, 1}};
        auto count_mines = [&](int x, int y) {
            int count = 0;
            for (auto d : dirs) {
                int nx = x + d.first, ny = y + d.second;
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && board[nx][ny] == 'M')
                    ++count;
            }
            return count;
        };

        int x = click[0], y = click[1];
        if (board[x][y] == 'M') {
            board[x][y] = 'X';
            return board;
        }
        queue<pair<int, int>> q;
        q.push({x, y});
        while (!q.empty()) {
            auto [cx, cy] = q.front(); q.pop();
            if (board[cx][cy] != 'E') continue;
            int mines = count_mines(cx, cy);
            if (mines == 0) {
                board[cx][cy] = 'B';
                for (auto d : dirs) {
                    int nx = cx + d.first, ny = cy + d.second;
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && board[nx][ny] == 'E')
                        q.push({nx, ny});
                }
            } else {
                board[cx][cy] = mines + '0';
            }
        }
        return board;
    }
};
      

class Solution {
    public char[][] updateBoard(char[][] board, int[] click) {
        int m = board.length, n = board[0].length;
        int[][] dirs = {{-1, -1}, {-1, 0}, {-1, 1},
                        {0, -1},           {0, 1},
                        {1, -1},  {1, 0},  {1, 1}};
        Queue<int[]> queue = new LinkedList<>();
        int x = click[0], y = click[1];
        if (board[x][y] == 'M') {
            board[x][y] = 'X';
            return board;
        }
        queue.offer(new int[]{x, y});
        while (!queue.isEmpty()) {
            int[] pos = queue.poll();
            int cx = pos[0], cy = pos[1];
            if (board[cx][cy] != 'E') continue;
            int mines = 0;
            for (int[] d : dirs) {
                int nx = cx + d[0], ny = cy + d[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && board[nx][ny] == 'M')
                    mines++;
            }
            if (mines == 0) {
                board[cx][cy] = 'B';
                for (int[] d : dirs) {
                    int nx = cx + d[0], ny = cy + d[1];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && board[nx][ny] == 'E')
                        queue.offer(new int[]{nx, ny});
                }
            } else {
                board[cx][cy] = (char) (mines + '0');
            }
        }
        return board;
    }
}
      

var updateBoard = function(board, click) {
    const m = board.length, n = board[0].length;
    const dirs = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];
    const countMines = (x, y) => {
        let count = 0;
        for (const [dx, dy] of dirs) {
            const nx = x + dx, ny = y + dy;
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && board[nx][ny] === 'M')
                count++;
        }
        return count;
    };
    const [x, y] = click;
    if (board[x][y] === 'M') {
        board[x][y] = 'X';
        return board;
    }
    const queue = [[x, y]];
    while (queue.length) {
        const [cx, cy] = queue.shift();
        if (board[cx][cy] !== 'E') continue;
        const mines = countMines(cx, cy);
        if (mines === 0) {
            board[cx][cy] = 'B';
            for (const [dx, dy] of dirs) {
                const nx = cx + dx, ny = cy + dy;
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && board[nx][ny] === 'E')
                    queue.push([nx, ny]);
            }
        } else {
            board[cx][cy] = mines.toString();
        }
    }
    return board;
};
      

Problem Description

You are given a 2D character matrix board representing a Minesweeper game. Each cell can be:

• 'M': An unrevealed mine
• 'E': An unrevealed empty square
• 'B': A revealed blank square with no adjacent mines
• '1' to '8': A revealed square with the digit indicating the number of adjacent mines
• 'X': A revealed mine (when clicked)

The update rules are:

• If a mine ('M') is revealed, change it to 'X' and stop.
• If an empty square ('E') is revealed:
  • If it has adjacent mines, reveal it as the digit ('1'-'8').
  • If it has no adjacent mines, reveal it as 'B' and recursively reveal all adjacent unrevealed squares.

Thought Process

To solve this problem, we need to simulate the behavior of the Minesweeper game when a user clicks on a cell. The naive approach would be to check the clicked cell and, if it's empty, recursively (or iteratively) reveal all connected empty cells, just like the real game. The challenge is to efficiently handle the recursive revealing, especially to avoid redundant work and infinite loops.

A brute-force solution might use a simple recursive function to reveal each cell, but this could lead to stack overflow for large boards. An optimized approach is to use Breadth-First Search (BFS) with a queue to iteratively process cells, ensuring we don't process the same cell more than once. We also need to correctly count adjacent mines for each cell and update the board accordingly.

The key insight is that only unrevealed empty cells ('E') need to be processed, and once a cell is revealed, it should not be processed again. We must also handle edge cases, such as clicking on a mine or on a cell at the edge of the board.

Solution Approach

The solution uses Breadth-First Search (BFS) to avoid recursion depth issues and to efficiently reveal all connected empty cells. Here are the steps:

1. Check the Clicked Cell:
   • If the clicked cell is a mine ('M'), change it to 'X' and return the board immediately.
2. Initialize BFS:
   • Use a queue to keep track of cells to process. Start with the clicked cell.
3. Process Each Cell:
   • While the queue is not empty, pop a cell from the queue.
   • If the cell is not 'E', skip it (already revealed or processed).
   • Count the number of adjacent mines by checking all 8 neighboring cells.
   • If there are adjacent mines:
     • Set the cell to the digit ('1'-'8') representing the count.
   • If there are no adjacent mines:
     • Set the cell to 'B'.
     • Add all adjacent unrevealed empty cells ('E') to the queue for further processing.
4. Return the Board:
   • After processing, return the updated board.

We use a queue (BFS) instead of recursion to avoid stack overflow and to ensure we process each cell only once. We use direction vectors to check all 8 neighbors for mines. This approach is efficient and handles all edge cases.

Example Walkthrough

Consider the following board:

• [ ['E', 'E', 'E', 'E', 'E'], ['E', 'E', 'M', 'E', 'E'], ['E', 'E', 'E', 'E', 'E'], ['E', 'E', 'E', 'E', 'E'] ]

Suppose the click is [3, 0] (bottom-left corner).

1. The clicked cell is 'E' and has 0 adjacent mines, so it's set to 'B'. All neighbors are added to the queue.
2. The neighbors are processed one by one. For each, count adjacent mines:
   • If adjacent mines exist, set the cell to the count and do not add its neighbors.
   • If no adjacent mines, set to 'B' and add its neighbors.
3. This process continues, revealing a region of 'B's and numbers around the mine at (1, 2).

The final board after the click looks like: [ ['B', '1', 'E', '1', 'B'], ['B', '1', 'M', '1', 'B'], ['B', '1', '1', '1', 'B'], ['B', 'B', 'B', 'B', 'B'] ]

Note how only the region connected to the click is revealed, and numbers are shown only where adjacent mines exist.

Time and Space Complexity

• Brute-force (Recursive DFS):
  • Time Complexity: O(mn) in the worst case, where m and n are the board dimensions, since each cell may be visited once.
  • Space Complexity: O(mn) due to recursion stack and potential queue size.
• Optimized BFS Approach:
  • Time Complexity: O(mn) in the worst case, as each cell is put into the queue at most once.
  • Space Complexity: O(mn) for the queue in the worst case (when all cells are empty and connected).

The BFS approach avoids stack overflow and is efficient for large boards.

Summary

The Minesweeper problem simulates the classic game's cell revealing logic. By using BFS, we efficiently reveal all connected empty cells and correctly display numbers for cells adjacent to mines. The key insights are to process each cell only once, use a queue to avoid recursion depth issues, and handle all edge cases. This approach is both elegant and practical for large boards, providing a clear and maintainable solution.