Minesweeper

medium dfs bfs matrix

Problem

Given an m×n board of 'M' (mine), 'E' (unrevealed empty), 'B' (revealed blank), '1'–'8' (count), 'X' (clicked mine), and a click position, update the board: clicking a mine reveals X and ends. Clicking an empty cell reveals it: if it has adjacent mines, show the count; otherwise flood-fill all blank neighbours.

Inputboard = [[E,E,E],[E,M,E],[E,E,E]], click = (0,0)

Output[[B,B,B],[1,1,1],[1,M,1] partial flood]

Flood reveals blanks; cells next to a mine display the count and stop the flood.

board (rows separated by ';', use M/E)

row

col

def update_board(board, click):
    r, c = click
    if board[r][c] == 'M':
        board[r][c] = 'X'
        return board
    m, n = len(board), len(board[0])
    DIRS = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
    def dfs(i, j):
        if board[i][j] != 'E':
            return
        mines = sum(1 for di, dj in DIRS
                    if 0 <= i+di < m and 0 <= j+dj < n
                    and board[i+di][j+dj] == 'M')
        if mines:
            board[i][j] = str(mines)
            return
        board[i][j] = 'B'
        for di, dj in DIRS:
            if 0 <= i+di < m and 0 <= j+dj < n:
                dfs(i+di, j+dj)
    dfs(r, c)
    return board

function updateBoard(board, click) {
  const [r, c] = click;
  if (board[r][c] === 'M') { board[r][c] = 'X'; return board; }
  const m = board.length, n = board[0].length;
  const DIRS = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];
  function dfs(i, j) {
    if (board[i][j] !== 'E') return;
    let mines = 0;
    for (const [di, dj] of DIRS) {
      const ni = i+di, nj = j+dj;
      if (ni>=0 && ni<m && nj>=0 && nj<n && board[ni][nj]==='M') mines++;
    }
    if (mines) { board[i][j] = String(mines); return; }
    board[i][j] = 'B';
    for (const [di, dj] of DIRS) {
      const ni = i+di, nj = j+dj;
      if (ni>=0 && ni<m && nj>=0 && nj<n) dfs(ni, nj);
    }
  }
  dfs(r, c);
  return board;
}

class Solution {
    int[][] DIRS = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
    public char[][] updateBoard(char[][] board, int[] click) {
        int r = click[0], c = click[1];
        if (board[r][c] == 'M') { board[r][c] = 'X'; return board; }
        dfs(board, r, c);
        return board;
    }
    private void dfs(char[][] b, int i, int j) {
        if (b[i][j] != 'E') return;
        int m = b.length, n = b[0].length, mines = 0;
        for (int[] d : DIRS) {
            int ni = i+d[0], nj = j+d[1];
            if (ni>=0 && ni<m && nj>=0 && nj<n && b[ni][nj]=='M') mines++;
        }
        if (mines > 0) { b[i][j] = (char)('0' + mines); return; }
        b[i][j] = 'B';
        for (int[] d : DIRS) {
            int ni = i+d[0], nj = j+d[1];
            if (ni>=0 && ni<m && nj>=0 && nj<n) dfs(b, ni, nj);
        }
    }
}

vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
    int r = click[0], c = click[1];
    if (board[r][c] == 'M') { board[r][c] = 'X'; return board; }
    int m = board.size(), n = board[0].size();
    int DIRS[8][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
    function<void(int,int)> dfs = [&](int i, int j) {
        if (board[i][j] != 'E') return;
        int mines = 0;
        for (auto& d : DIRS) {
            int ni = i+d[0], nj = j+d[1];
            if (ni>=0 && ni<m && nj>=0 && nj<n && board[ni][nj]=='M') mines++;
        }
        if (mines) { board[i][j] = '0' + mines; return; }
        board[i][j] = 'B';
        for (auto& d : DIRS) {
            int ni = i+d[0], nj = j+d[1];
            if (ni>=0 && ni<m && nj>=0 && nj<n) dfs(ni, nj);
        }
    };
    dfs(r, c);
    return board;
}

Explanation

This mimics what happens when you click a cell in Minesweeper. There are two cases: you clicked a mine, or you clicked an empty cell that triggers a reveal.

If the clicked cell is 'M', we simply mark it 'X' and the game is over. Otherwise we run a flood-fill DFS from the click.

For each empty cell 'E' the DFS visits, it counts the mines in the 8 surrounding cells. If that count is positive, the cell shows that digit and the flood stops there — a numbered cell acts as a wall. If the count is zero, the cell becomes a blank 'B' and we recurse into all 8 neighbors to keep revealing.

The if board[i][j] != 'E' guard at the top stops us from re-processing cells already revealed, which prevents infinite loops.

Example: clicking an empty corner with no nearby mines turns it to 'B' and spreads outward, stopping at cells touching the mine, which display '1'.

Time: O(m·n) Space: O(m·n)