# Solution For Minesweeper

The Minesweeper problem on LeetCode is a classic problem that involves using concepts of graph and BFS traversal. In this problem, we are given a 2D grid representing a Minesweeper game. Our goal is to uncover all the mines present in the grid, given that the mines are represented by ‘M’ and all the empty cells are represented by ‘E’. Initially, all the cells in the grid are covered, and we start by clicking on a cell.

If the clicked cell is empty, then all its adjacent cells are also uncovered recursively, until we reach the cells that are adjacent to mine cells. If the clicked cell is a mine, the game is over, and all the mine cells are uncovered.

We are supposed to implement a function ‘updateBoard(board: List[List[str]], click: List[int]) -> List[List[str]]’ that takes in a 2D grid, ‘board’ and the coordinates of the cell clicked as a list of two integers, ‘click’. The function returns a modified ‘board’ that includes the newly uncovered cells.

Here’s the detailed solution to the Minesweeper problem on LeetCode.

Approach:

1. Create a queue and add the cell clicked to the queue.
2. While the queue is not empty, dequeue a cell.
3. If the dequeued cell is a mine, mark it as ‘X’, and the game is over.
4. If the dequeued cell is empty, uncover it by marking it as ‘B’.
5. Count the number of mines present in its adjacent cells.
6. If any adjacent cell has a mine, mark the current cell with the count of mines.
7. If the adjacent cell is empty and unexplored, add it to the queue.

Implementation:

“`
from typing import List

def updateBoard(board: List[List[str]], click: List[int]) -> List[List[str]]:
m, n = len(board), len(board[0])
row, col = click[0], click[1] if board[row][col] == ‘M’:
board[row][col] = ‘X’
return board

``````q = [(row, col)]
while q:
x, y = q.pop(0)
if board[x][y] == 'E':
count = 0
directions = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)]
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and board[nx][ny] == 'M':
count += 1
if count > 0:
board[x][y] = str(count)
else:
board[x][y] = 'B'
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and board[nx][ny] == 'E':
q.append((nx, ny))
return board
``````

“`

In the above implementation, we first find the dimensions of the given board, and the row and col coordinates of the clicked cell. We then create a queue and add the clicked cell to the queue.

Inside the while loop, we dequeue a cell and check if it is empty (‘E’) or a mine (‘M’). If it is a mine, we mark it as ‘X’ and return the modified board.

If it is an empty cell, we count the number of mines present in its adjacent cells. We do this by iterating over all the adjacent cells using a list of tuples representing their relative positions. If we find a mine in any adjacent cell, we increment the count.

If the count is greater than 0, we mark the current cell with the count as a string.

If the count is 0, we mark the current cell as ‘B’, indicating that it is empty. We then add all the adjacent cells that are empty and have not been explored yet to the queue.

We continue this process until the queue is empty, and finally return the modified board.

Time Complexity:
In the worst-case scenario, we might explore all the cells in the grid, so the time complexity of this algorithm is O(m*n).

Space Complexity:
The maximum size of the queue could be O(mn), leading to space complexity as O(mn).

This is the solution to the Minesweeper problem on LeetCode.

## Step by Step Implementation For Minesweeper

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

if (board[row][col] == 'M') { // Mine
board[row][col] = 'X';
}
else { // Empty
// Get number of mines first.
int count = 0;
for (int i = -1; i < 2; i++) {
for (int j = -1; j < 2; j++) {
if (i == 0 && j == 0) continue;
int r = row + i, c = col + j;
if (r < 0 || r >= m || c < 0 || c >= n) continue;
if (board[r][c] == 'M' || board[r][c] == 'X') count++;
}
}

if (count > 0) { // If it is not a 'B', stop further DFS.
board[row][col] = (char)(count + '0');
}
else { // Continue DFS to adjacent cells.
board[row][col] = 'B';
for (int i = -1; i < 2; i++) {
for (int j = -1; j < 2; j++) {
if (i == 0 && j == 0) continue;
int r = row + i, c = col + j;
if (r < 0 || r >= m || c < 0 || c >= n) continue;
if (board[r][c] == 'E') {
updateBoard(board, new int[] {r, c});
}
}
}
}
}

return board;
}
}```
```class Solution:
def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:

# Get the dimensions of the board
rows = len(board)
cols = len(board[0])

# Perform a DFS from the given click position
self.dfs(board, rows, cols, click[0], click[1])

return board

def dfs(self, board: List[List[str]], rows: int, cols: int, i: int, j: int):

# Base case: If the position is out of bounds or is already revealed, return
if i < 0 or i >= rows or j < 0 or j >= cols or board[i][j] != 'E':
return

# Get the number of mines around the current position
num_mines = self.get_num_mines(board, rows, cols, i, j)

# If there are no mines around the current position, reveal all 8 positions around it
if num_mines == 0:
board[i][j] = 'B'
self.dfs(board, rows, cols, i-1, j-1)
self.dfs(board, rows, cols, i-1, j)
self.dfs(board, rows, cols, i-1, j+1)
self.dfs(board, rows, cols, i, j-1)
self.dfs(board, rows, cols, i, j+1)
self.dfs(board, rows, cols, i+1, j-1)
self.dfs(board, rows, cols, i+1, j)
self.dfs(board, rows, cols, i+1, j+1)
# Otherwise, just reveal the number of mines around the current position
else:
board[i][j] = str(num_mines)

return

def get_num_mines(self, board: List[List[str]], rows: int, cols: int, i: int, j: int):

# Variable to keep track of the number of mines around the current position
num_mines = 0

# Check all 8 positions around the current position
for x in range(i-1, i+2):
for y in range(j-1, j+2):

# If the position is out of bounds, continue
if x < 0 or x >= rows or y < 0 or y >= cols:
continue

# If the position is a mine, increment the counter
if board[x][y] == 'M':
num_mines += 1

return num_mines```
```var minesweeper = function(board, click) {
var row = click[0];
var col = click[1];

// check if the click is valid
if (row < 0 || row >= board.length || col < 0 || col >= board[0].length) {
return;
}

// check if the cell is already revealed or is a mine
if (board[row][col] !== 'E' && board[row][col] !== 'M') {
return;
}

// check if the cell is a mine
if (board[row][col] === 'M') {
// reveal the cell as a mine
board[row][col] = 'X';
return;
}

// initialize variables
var mines = 0;
var queue = [];

// check all adjacent cells for mines
for (var i = -1; i <= 1; i++) {
for (var j = -1; j <= 1; j++) {
if (i === 0 && j === 0) {
continue;
}

var r = row + i;
var c = col + j;

// check if adjacent cell is valid
if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) {
continue;
}

// check if adjacent cell is a mine
if (board[r][c] === 'M') {
mines++;
}
}
}

if (mines === 0) {
queue.push([row, col]);
}

// reveal cell
board[row][col] = mines === 0 ? 'B' : mines;

// while queue is not empty
while (queue.length > 0) {
// dequeue cell
var cell = queue.shift();
var r = cell[0];
var c = cell[1];

for (var i = -1; i <= 1; i++) {
for (var j = -1; j <= 1; j++) {
if (i === 0 && j === 0) {
continue;
}

var nr = r + i;
var nc = c + j;

// check if adjacent cell is valid
if (nr < 0 || nr >= board.length || nc < 0 || nc >= board[0].length) {
continue;
}

// check if adjacent cell is already revealed or is a mine
if (board[nr][nc] !== 'E' && board[nr][nc] !== 'M') {
continue;
}

minesweeper(board, [nr, nc]);
}
}
}
};```
```class Solution {
public:
vector> updateBoard(vector>& board, vector& click) {
int m = board.size(), n = board[0].size();
int row = click[0], col = click[1];

if (board[row][col] == 'M') { // Mine
board[row][col] = 'X';
}
else { // Empty
// Get number of mines first.
int count = 0;
for (int i = -1; i < 2; i++) {
for (int j = -1; j < 2; j++) {
if (i == 0 && j == 0) continue;
int r = row + i, c = col + j;
if (r < 0 || r >= m || c < 0 || c >= n) continue;
if (board[r][c] == 'M' || board[r][c] == 'X') count++;
}
}

if (count > 0) { // If it is not a 'B', stop further DFS.
board[row][col] = count + '0';
}
else { // Continue DFS to adjacent cells.
board[row][col] = 'B';
for (int i = -1; i < 2; i++) {
for (int j = -1; j < 2; j++) {
if (i == 0 && j == 0) continue;
int r = row + i, c = col + j;
if (r < 0 || r >= m || c < 0 || c >= n) continue;
if (board[r][c] == 'E') {
updateBoard(board, {r, c});
}
}
}
}
}

return board;
}
};```
```using System;

public class Solution {

// Create a 2D array of char with ' ' as default value
public static char[,] CreateBoard(int rows, int cols)
{
var board = new char[rows, cols];

for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
board[i, j] = ' ';
}
}

return board;
}

// Print the 2D array
public static void PrintBoard(char[,] board)
{
for (int i = 0; i < board.GetLength(0); i++)
{
for (int j = 0; j < board.GetLength(1); j++)
{
Console.Write(board[i, j]);
}

Console.WriteLine();
}
}

// Place mines on the board
public static void PlaceMines(char[,] board, int[,] mines)
{
for (int i = 0; i < mines.GetLength(0); i++)
{
int row = mines[i, 0];
int col = mines[i, 1];

board[row, col] = '*';
}
}

// Calculate the number of mines around each cell
public static void CalculateHints(char[,] board)
{
for (int i = 0; i < board.GetLength(0); i++)
{
for (int j = 0; j < board.GetLength(1); j++)
{
if (board[i, j] != '*')
{
board[i, j] = CountMines(board, i, j);
}
}
}
}

// Count the number of mines around the given cell
public static char CountMines(char[,] board, int row, int col)
{
int count = 0;

for (int i = row - 1; i <= row + 1; i++)
{
for (int j = col - 1; j <= col + 1; j++)
{
if (i >= 0 && i < board.GetLength(0) && j >= 0 && j < board.GetLength(1))
{
if (board[i, j] == '*')
{
count++;
}
}
}
}

return char.Parse(count.ToString());
}

public static void Main()
{
// Input
int rows = 5;
int cols = 5;
int[,] mines = new int[3, 2] { { 1, 1 }, { 2, 2 }, { 0, 4 } };

// Output
var board = CreateBoard(rows, cols);
PlaceMines(board, mines);
CalculateHints(board);
PrintBoard(board);
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]