You are given a 2D grid representing a Minesweeper game. The grid contains the following characters:
'M': Represents a mine.'E': Represents an empty cell.'B': Represents a cell that has not been revealed yet.- A digit character
'1'to'8': Represents the number of adjacent mines.
You need to reveal the cells of the grid according to the following rules:
- If the cell contains a mine (
'M'), it should be changed to'X', and the game is over. - If the cell is an empty cell (
'E') and has no adjacent mines, it should be changed to'B', and all its adjacent cells should be recursively revealed. - If the cell is an empty cell (
'E') and has adjacent mines, it should be changed to the digit representing the number of adjacent mines.
You need to return the final state of the board after all the cells have been revealed.
Table of Contents
Sample 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]
Expected Output:
Result:
[
['B', '1', 'E', '1', 'B'],
['B', '1', 'M', '1', 'B'],
['B', '1', '1', '1', 'B'],
['B', 'B', 'B', 'B', 'B']
]
In this example, the function will reveal the cells of the Minesweeper game board according to the rules, and the output will be as shown.
Time and Space Complexity:
The time complexity of the algorithm is O(m * n), where ‘m’ is the number of rows and ‘n’ is the number of columns in the grid. In the worst case, we may have to visit each cell once to reveal all cells and recursively explore all adjacent empty cells.
The space complexity is O(m * n) as well, due to the recursion stack, which can grow to the size of the grid in the worst case.
C++ solution:
#include <iostream>
#include <vector>
// Define the four possible directions: up, down, left, right
std::vector<int> directions = {-1, 0, 1, 0, -1};
void revealEmptyCells(std::vector<std::vector<char>>& board, int row, int col) {
int rows = board.size();
int cols = board[0].size();
// Base case: If the current cell is out of bounds or it has been revealed, return.
if (row < 0 || row >= rows || col < 0 || col >= cols || board[row][col] != 'E') {
return;
}
// Count the number of adjacent mines.
int adjacentMines = 0;
for (int k = 0; k < 4; ++k) {
int newRow = row + directions[k];
int newCol = col + directions[k + 1];
if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && board[newRow][newCol] == 'M') {
adjacentMines++;
}
}
if (adjacentMines > 0) {
// If the current cell has adjacent mines, update it with the count of adjacent mines.
board[row][col] = '0' + adjacentMines;
} else {
// If the current cell is an empty cell with no adjacent mines, reveal it ('B') and explore its neighbors.
board[row][col] = 'B';
for (int k = 0; k < 4; ++k) {
revealEmptyCells(board, row + directions[k], col + directions[k + 1]);
}
}
}
std::vector<std::vector<char>> updateBoard(std::vector<std::vector<char>>& board, std::vector<int>& click) {
int row = click[0];
int col = click[1];
// Base case: If the click is on a mine, mark it as 'X' and return.
if (board[row][col] == 'M') {
board[row][col] = 'X';
return board;
}
// If the click is on an empty cell, reveal the cells and return the updated board.
revealEmptyCells(board, row, col);
return board;
}
int main() {
// Construct the board for the sample input
std::vector<std::vector<char>> board = {
{'E', 'E', 'E', 'E', 'E'},
{'E', 'E', 'M', 'E', 'E'},
{'E', 'E', 'E', 'E', 'E'},
{'E', 'E', 'E', 'E', 'E'}
};
std::vector<int> click = {3, 0};
// Update the Minesweeper board based on the click
std::vector<std::vector<char>> updatedBoard = updateBoard(board, click);
// Print the result
std::cout << "Result:" << std::endl;
for (const auto& row : updatedBoard) {
std::cout << "[";
for (int i = 0; i < row.size(); ++i) {
std::cout << row[i];
if (i < row.size() - 1) {
std::cout << ", ";
}
}
std::cout << "]" << std::endl;
}
return 0;
}
The revealEmptyCells function is a helper function that performs a depth-first search (DFS) to reveal all adjacent empty cells and update them with the number of adjacent mines. It starts from a given empty cell and recursively explores all its adjacent cells (top, bottom, left, right). If the current cell has adjacent mines, it updates it with the count of adjacent mines. Otherwise, it reveals the current cell (‘B’) and continues to explore its neighbors.
The updateBoard function is the entry point of the algorithm. It handles the click and updates the Minesweeper board based on the rules. If the click is on a mine, it marks it as ‘X’ and returns the board. If the click is on an empty cell, it reveals the cells and returns the updated board.
In the given example, the function will correctly update the Minesweeper board based on the click, and the output will be as shown.