MineSweeper

118.Minesweeper

Matrix

Depth First Search

Problem Statement:

Given a 2D char matrix board representing a Minesweeper game board and a click position, implement the Minesweeper game logic to update the board. The possible states of the board are:

• 'M': A mine.
• 'E': An empty cell.
• 'B': An empty cell with no adjacent mines.
• '1' - '8': An empty cell with the number of adjacent mines.
• 'X': A revealed mine (caused by clicking on a mine).

Given a click position, reveal the board and return the updated board.

Algorithm:

1. Check the clicked cell:
   • If it's a mine ('M'), change it to 'X' and return the board.
   • If it's an empty cell ('E'), recursively reveal adjacent cells using DFS.
2. During DFS:
   • Count adjacent mines. If there are any, update the cell with the count.
   • If no adjacent mines exist, mark the cell as 'B' and recursively process all adjacent cells.
3. Use a helper function to calculate the number of adjacent mines for a cell.

Complexity:

Time: O(m × n), where m is the number of rows and n is the number of columns | Space: O(m × n) for the recursion stack.

Java Implementation:

public class Solution {
    public char[][] updateBoard(char[][] board, int[] click) {
        int i = click[0], j = click[1];
        if (board[i][j] == 'M') {
            board[i][j] = 'X'; // Reveal mine
        } else {
            dfs(board, i, j, board.length, board[0].length);
        }
        return board;
    }

    private void dfs(char[][] board, int i, int j, int m, int n) {
        if (board[i][j] != 'E') return;

        int count = adjacentMines(board, i, j, m, n);

        if (count > 0) {
            board[i][j] = (char) (count + '0'); // Show number of adjacent mines
        } else {
            board[i][j] = 'B'; // Mark as blank
            for (int dx = -1; dx <= 1; dx++) {
                for (int dy = -1; dy <= 1; dy++) {
                    if (dx == 0 && dy == 0) continue;
                    int newX = i + dx, newY = j + dy;
                    if (newX >= 0 && newX < m && newY >= 0 && newY < n) {
                        dfs(board, newX, newY, m, n);
                    }
                }
            }
        }
    }

    private int adjacentMines(char[][] board, int i, int j, int m, int n) {
        int count = 0;
        for (int dx = -1; dx <= 1; dx++) {
            for (int dy = -1; dy <= 1; dy++) {
                if (dx == 0 && dy == 0) continue;
                int newX = i + dx, newY = j + dy;
                if (newX >= 0 && newX < m && newY >= 0 && newY < n && board[newX][newY] == 'M') {
                    count++;
                }
            }
        }
        return count;
    }
}
                

Python Implementation:

def updateBoard(board, click):
    i, j = click
    if board[i][j] == 'M':
        board[i][j] = 'X' # Reveal mine
    else:
        dfs(board, i, j, len(board), len(board[0]))
    return board

def dfs(board, i, j, m, n):
    if board[i][j] != 'E':
        return

    count = adjacent_mines(board, i, j, m, n)

    if count > 0:
        board[i][j] = str(count) # Show number of adjacent mines
    else:
        board[i][j] = 'B' # Mark as blank
        for dx in range(-1, 2):
            for dy in range(-1, 2):
                if dx == 0 and dy == 0:
                    continue
                new_x, new_y = i + dx, j + dy
                if 0 <= new_x < m and 0 <= new_y < n:
                    dfs(board, new_x, new_y, m, n)

def adjacent_mines(board, i, j, m, n):
    count = 0
    for dx in range(-1, 2):
        for dy in range(-1, 2):
            if dx == 0 and dy == 0:
                continue
            new_x, new_y = i + dx, j + dy
            if 0 <= new_x < m and 0 <= new_y < n and board[new_x][new_y] == 'M':
                count += 1
    return count
                

C++ Implementation:

class Solution {
public:
    vector> updateBoard(vector>& board, vector& click) {
        int i = click[0], j = click[1];
        if (board[i][j] == 'M') {
            board[i][j] = 'X'; // Reveal mine
        } else {
            dfs(board, i, j, board.size(), board[0].size());
        }
        return board;
    }

    void dfs(vector>& board, int i, int j, int m, int n) {
        if (board[i][j] != 'E') return;

        int count = adjacentMines(board, i, j, m, n);

        if (count > 0) {
            board[i][j] = '0' + count; // Show number of adjacent mines
        } else {
            board[i][j] = 'B'; // Mark as blank
            for (int dx = -1; dx <= 1; dx++) {
                for (int dy = -1; dy <= 1; dy++) {
                    if (dx == 0 && dy == 0) continue;
                    int newX = i + dx, newY = j + dy;
                    if (newX >= 0 && newX < m && newY >= 0 && newY < n) {
                        dfs(board, newX, newY, m, n);
                    }
                }
            }
        }
    }

    int adjacentMines(vector>& board, int i, int j, int m, int n) {
        int count = 0;
        for (int dx = -1; dx <= 1; dx++) {
            for (int dy = -1; dy <= 1; dy++) {
                if (dx == 0 && dy == 0) continue;
                int newX = i + dx, newY = j + dy;
                if (newX >= 0 && newX < m && newY >= 0 && newY < n && board[newX][newY] == 'M') {
                    count++;
                }
            }
        }
        return count;
    }
};