algoadvance

Leetcode 529. Minesweeper

Problem Statement

Leetcode Problem 529: Minesweeper

You are given a 2D char matrix representing the game board. M represents a mine, E represents an empty cell, B represents a blank cell (i.e., one that doesn’t have any adjacent mines), and numbers from ‘1’ to ‘8’ represent cells with that many mines adjacent to it. The game character initially opens a cell represented by the given tuple click (row, column) of the board.

When a cell containing a mine (‘M’) is revealed, the game is over. Otherwise, if an empty cell (‘E’) with no adjacent mines is revealed, it becomes a blank cell (‘B’) and all of its adjacent cells are recursively revealed. If an empty cell with at least one adjacent mine is revealed, it shows the number of adjacent mines.

Write a function to play the Minesweeper game according to the above rules:

vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click);

Example:

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']]

Clarifying Questions

  1. Can the board have non-rectangular shapes (i.e., rows of different lengths)?
  2. Are there any constraints on the size of the board?
  3. Can the click point be on a mine initially?
  4. Should the input be validated for invalid click locations?

Strategy

  1. Determine Base Case:
    • If the initial click is on a mine M, convert it to X indicating game over.
  2. Handle the Recursive Case:
    • For each non-mine cell, perform a Depth First Search (DFS) or Breadth First Search (BFS).
    • Either reveal mines around or convert empty cells to blank cells B and recursively reveal their neighbors.
  3. DFS/BFS Approach:
    • Use a stack/queue to iteratively reveal cells to avoid recursion depth issues.
    • Check all 8 neighbors for each cell.
    • Update counts or reveal cells based on mine proximity.

Time Complexity

Code

#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        int directions[8][2] = \{\{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
        int rows = board.size();
        int cols = board[0].size();
        int rowClick = click[0];
        int colClick = click[1];
        
        // If initial click is on a mine, game over.
        if (board[rowClick][colClick] == 'M') {
            board[rowClick][colClick] = 'X';
            return board;
        }
        
        // Helper function to count mines around a cell
        auto countMines = [&](int row, int col) -> int {
            int count = 0;
            for (auto dir : directions) {
                int newRow = row + dir[0];
                int newCol = col + dir[1];
                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && board[newRow][newCol] == 'M') {
                    count++;
                }
            }
            return count;
        };
        
        // Use a queue for BFS
        queue<pair<int, int>> toCheck;
        toCheck.push({rowClick, colClick});
        
        while (!toCheck.empty()) {
            auto [currentRow, currentCol] = toCheck.front();
            toCheck.pop();
            
            // Count adjacent mines
            int mineCount = countMines(currentRow, currentCol);
            if (mineCount > 0) {
                board[currentRow][currentCol] = '0' + mineCount;
            } else {
                board[currentRow][currentCol] = 'B';
                for (auto dir : directions) {
                    int newRow = currentRow + dir[0];
                    int newCol = currentCol + dir[1];
                    if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && board[newRow][newCol] == 'E') {
                        board[newRow][newCol] = 'B';  // Prevent re-adding to the queue
                        toCheck.push({newRow, newCol});
                    }
                }
            }
        }
        
        return board;
    }
};

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI