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 there are no adjacent mines, add cell to queue
    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];
        
        // check all adjacent cells
        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;
                }
                
                // recurse on adjacent cell
                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); 
} 
}