Minesweeper

Let's play the minesweeper game (Wikipedia, online game)!

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.

For example, consider the following board:
board = [["E","E","E","E","E"],["E","E","M","E","E"],["E","E","E","E","E"],["E","E","E","E","E"]]
If the click is click = [3,0], the expected output should be:
[["B","1","E","1","B"],["B","1","M","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]]

Write a function to implement the minesweeper game logic given a board and a click. Your function should efficiently reveal squares according to the described rules, taking into account cases such as clicking on a mine, an empty square, or a square with adjacent mines.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Minesweeper {
public:
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        int row = click[0];
        int col = click[1];

        if (board[row][col] == 'M') {
            board[row][col] = 'X';
            return board;
        }

        int m = board.size();
        int n = board[0].size();

        queue<pair<int, int>> q;
        q.push({row, col});

        while (!q.empty()) {
            pair<int, int> curr = q.front();
            q.pop();

            int r = curr.first;
            int c = curr.second;

            if (board[r][c] != 'E') continue;

            int count = countAdjacentMines(board, r, c);

            if (count > 0) {
                board[r][c] = count + '0';
            } else {
                board[r][c] = 'B';
                for (int i = -1; i <= 1; ++i) {
                    for (int j = -1; j <= 1; ++j) {
                        if (i == 0 && j == 0) continue;
                        int newRow = r + i;
                        int newCol = c + j;
                        if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && board[newRow][newCol] == 'E') {
                            q.push({newRow, newCol});
                        }
                    }
                }
            }
        }
        return board;
    }

private:
    int countAdjacentMines(vector<vector<char>>& board, int row, int col) {
        int count = 0;
        int m = board.size();
        int n = board[0].size();
        for (int i = -1; i <= 1; ++i) {
            for (int j = -1; j <= 1; ++j) {
                if (i == 0 && j == 0) continue;
                int newRow = row + i;
                int newCol = col + j;
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && board[newRow][newCol] == 'M') {
                    count++;
                }
            }
        }
        return count;
    }
};

int main() {
    Minesweeper ms;
    vector<vector<char>> board1 = {{
        {'E','E','E','E','E'},
        {'E','E','M','E','E'},
        {'E','E','E','E','E'},
        {'E','E','E','E','E'}
    }};
    vector<int> click1 = {3, 0};
    vector<vector<char>> result1 = ms.updateBoard(board1, click1);
    cout << "Example 1:" << endl;
    for (const auto& row : result1) {
        for (char c : row) {
            cout << c << " ";
        }
        cout << endl;
    }
    cout << endl;

    vector<vector<char>> board2 = {{
        {'B','1','E','1','B'},
        {'B','1','M','1','B'},
        {'B','1','1','1','B'},
        {'B','B','B','B','B'}
    }};
    vector<int> click2 = {1, 2};
    vector<vector<char>> result2 = ms.updateBoard(board2, click2);
    cout << "Example 2:" << endl;
    for (const auto& row : result2) {
        for (char c : row) {
            cout << c << " ";
        }
        cout << endl;
    }
    cout << endl;

    return 0;
}

Naive Solution

The naive solution would involve iterating through the entire board for each click, which is not efficient. For each 'E', we would need to check all its neighbors. This approach doesn't leverage the recursive nature of revealing empty squares effectively.

Optimal Solution

The optimal solution uses Depth-First Search (DFS) or Breadth-First Search (BFS) to reveal the board efficiently. When a click hits an empty square, we count the adjacent mines. If there are no adjacent mines, we reveal all adjacent squares recursively.

The C++ code above implements the BFS approach:

1. If a mine 'M' is clicked, change it to 'X' and return the board.
2. If an empty square 'E' is clicked:
   • Count the number of adjacent mines.
   • If the count is greater than 0, change the square to the count and return the board.
   • If the count is 0, change the square to 'B' and recursively reveal all adjacent squares.

Big(O) Run-time Analysis

The time complexity is O(M * N) in the worst case, where M is the number of rows and N is the number of columns. This is because, in the worst-case scenario, we might need to visit every cell in the board (e.g., when clicking a large empty area).

Big(O) Space Usage Analysis

The space complexity is O(M * N) in the worst case. This is because the queue used in BFS could potentially contain all the 'E' cells on the board if a large area is clear. The call stack in DFS could also grow to O(M * N) in the worst-case scenario.

Edge Cases

1. Clicking a mine: The algorithm correctly handles clicking a mine by changing it to 'X' and terminating the game.
2. Clicking a revealed square: The algorithm should avoid processing already revealed squares (marked as 'B' or digits). The code checks for this with if (board[r][c] != 'E') continue;
3. Board with no mines: The algorithm correctly handles a board with no mines, revealing all empty squares.
4. Clicking on the border: The algorithm avoids out-of-bounds access by checking if newRow >= 0 && newRow < m && newCol >= 0 && newCol < n.
5. Large empty area: The BFS efficiently reveals large empty areas without stack overflow (which could occur with recursive DFS).
6. **Board Dimensions:**The code assumes the board dimensions are valid (m > 0, n > 0). If the board is empty (m = 0 or n = 0), the algorithm will still function, but no operations will occur, and the original board will be returned.
7. Click outside the board: The problem statement specified that the click coordinates are within the board. But, we could add an initial check if (row < 0 || row >= m || col < 0 || col >= n) return board; to handle cases where the click is outside the board boundaries.