Leetcode 529. Minesweeper

Problem Explanation

In Minesweeper, the game is played on a grid of squares (like the one shown above). Each square contains either a mine (represented by 'M') or no mine (represented by 'E'). If a square containing a mine is clicked, the game is over and the square is changed to 'X'. If a square without a mine is clicked, it is changed to either 'B' if it has no adjacent mines, or to a digit ('1' to '8') representing the number of adjacent mines. If the clicked square is revealed to be 'B', then all its adjacent squares are also revealed recursively.

Consider the example:

Input:

1[['E', 'E', 'E', 'E', 'E'],
2 ['E', 'E', 'M', 'E', 'E'],
3 ['E', 'E', 'E', 'E', 'E'],
4 ['E', 'E', 'E', 'E', 'E']]

Click : [3,0]

Output:

1[['B', '1', 'E', '1', 'B'],
2 ['B', '1', 'M', '1', 'B'],
3 ['B', '1', '1', '1', 'B'],
4 ['B', 'B', 'B', 'B', 'B']]

When we click on position [3,0] which is 'E', there are no mines in its adjacent squares hence we change it to 'B'. Since it's changed to 'B', all of its adjacent 'E' squares are revealed resulting in above output.

The task is to return the updated game board after a click on a given position.

Solution Approach

The solution uses Depth First Search (DFS) to visit all the squares which need to be revealed.

  1. If a mine ('M') is revealed, change it to 'X' and return the board.
  2. If an empty square ('E') with no adjacent mines is revealed, then change it to revealed blank ('B') and all of its adjacent unrevealed squares should be revealed recursively using DFS.
  3. If an empty square ('E') with at least one adjacent mine is revealed, then change it to a digit ('1' to '8') representing the number of adjacent mines.

Let's walk through the solution using the example:

Step 1: [['E', 'E', 'E', 'E', 'E'], ['E', 'E', 'M', 'E', 'E'], ['E', 'E', 'E', 'E', 'E'], ['E', 'E', 'E', 'E', 'E']]

Click : [3,0]

Step 2 (after DFS): [['B', '1', 'E', '1', 'B'], ['B', '1', 'M', '1', 'B'], ['B', '1', '1', '1', 'B'], ['B', 'B', 'B', 'B', 'B']]

Python Solution

The Python implementation of the above discussed solution:

1
2python
3class Solution:
4    def updateBoard(self, board, click):
5        (row, col), directions = click, ((-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1))
6        if 0 <= row < len(board) and 0 <= col < len(board[0]):
7            if board[row][col] == 'M':
8                board[row][col] = 'X'
9            elif board[row][col] =='E':
10                n = sum([board[row + r][col + c] == 'M' for r, c in directions if 0<= row + r < len(board) and 0 <= col + c < len(board[0])])
11                board[row][col] = str(n or 'B')
12                for r, c in directions * (not n): self.updateBoard(board, [row + r, col + c])
13        return board

Java Solution

Here is the Java implementation of the solution:

1
2java
3class Solution {
4    private final int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
5    public char[][] updateBoard(char[][] board, int[] click) {
6        int row = click[0], col = click[1];
7        if (board[row][col] == 'M') { // If it is a mine, change it to 'X' and return the board.
8            board[row][col] = 'X';
9        } else { // If it is not a mine, do DFS to reveal the squares.
10            dfs(board, row, col);
11        }
12        return board;
13    }
14    private void dfs(char[][] board, int row, int col) {
15        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length || board[row][col] != 'E') return;
16        int num = getMineNums(board, row, col);
17        if (num != 0) { // If it has adjacent mines, change it to digit and stop further DFS.
18            board[row][col] = (char) (num + '0');
19            return;
20        }
21        // If it has no adjacent mine, change it to 'B' and do further DFS to its neighbors.
22        board[row][col] = 'B';
23        for (int[] dir : dirs) dfs(board, row + dir[0], col + dir[1]);
24    }
25    private int getMineNums(char[][] board, int row, int col) {
26        int num = 0;
27        for (int[] dir : dirs) {
28            int newRow = row + dir[0], newCol = col + dir[1];
29            if (newRow < 0 || newRow >= board.length || newCol < 0 || newCol >= board[0].length) continue;
30            if (board[newRow][newCol] == 'M' || board[newRow][newCol] == 'X') num++;
31        }
32        return num;
33    }
34}

JavaScript Solution

Here is the JavaScript solution with the same approach:

1
2javascript
3/**
4 * @param {character[][]} board
5 * @param {number[]} click
6 * @return {character[][]}
7 */
8var updateBoard = function(board, click) {
9    let row = click[0],
10        col = click[1];
11
12    if (board[row][col] === 'M') {
13        board[row][col] = 'X';
14    } else {
15        dfs(board, row, col);
16    }
17
18    return board;
19};
20
21let dx = [-1, -1, -1, 0, 0, 1, 1, 1];
22let dy = [-1, 0, 1, -1, 1, -1, 0, 1];
23
24function dfs(board, row, col) {
25    let count = getMinesCount(board, row, col);
26
27    if (count === 0) {
28        board[row][col] = 'B';
29    } else {
30        board[row][col] = '' + count;
31        return;
32    }
33
34    for (let i = 0; i < 8; i++) {
35        let x = row + dx[i], y = col + dy[i];
36
37        if (x >= 0 && x < board.length && y >= 0 && y < board[0].length && board[x][y] === 'E') {
38            dfs(board, x, y);
39        }
40    }
41}
42
43function getMinesCount(board, row, col) {
44    let count = 0;
45
46    for (let i = 0; i < 8; i++) {
47        let x = row + dx[i], y = col + dy[i];
48
49        if (x >= 0 && x < board.length && y >= 0 && y < board[0].length && (board[x][y] === 'M' || board[x][y] === 'X')) {
50            count++;
51        }
52    }
53
54    return count;
55}

C++ Solution

Here's how we can implement the same approach in C++:

1
2c++
3class Solution {
4public:
5    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
6        int m = board.size(), n = board[0].size(), row = click[0], col = click[1], cnt = 0;
7        if (board[row][col] == 'M') { // Mine
8            board[row][col] = 'X';
9        } else { // Empty
10            // Get count of mines first.
11            for (int i = -1; i < 2; ++i) {
12                for (int j = -1; j < 2; ++j) {
13                    if (i == 0 && j == 0) continue;
14                    int nx = row + i, ny = col + j;
15                    if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
16                    // Only count the mines which are still hidden.
17                    if (board[nx][ny] == 'M' || board[nx][ny] == 'X') ++cnt;
18                }
19            }
20            if (cnt > 0) { // If it is not a 'B', stop further DFS.
21                board[row][col] = cnt + '0';
22            } else { // Continue DFS to adjacent cells.
23                board[row][col] = 'B';
24                for (int i = -1; i < 2; ++i) {
25                    for (int j = -1; j < 2; ++j) {
26                        if (i == 0 && j == 0) continue;
27                        int nx = row + i, ny = col + j;
28                        if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
29                        if (board[nx][ny] == 'E') updateBoard(board, vector<int>{nx, ny});
30                    }
31                }
32            }
33        }
34        return board;
35    }
36};

C# Solution

Here is the C# solution with the same approach:

1
2csharp
3public class Solution {
4    private static readonly int[] dx = new int [] { -1, -1, -1, 0, 0, 1, 1, 1 };
5    private static readonly int[] dy = new int [] { -1, 0, 1, -1, 1, -1, 0, 1 };
6
7    public char[][] UpdateBoard(char[][] board, int[] click) {
8        if (board[click[0]][click[1]] == 'M') {
9            board[click[0]][click[1]] = 'X';
10        } else {
11            DFS(board, click[0], click[1]);
12        }
13        return board;
14    }
15
16    private void DFS(char[][] board, int row, int col) {
17        int cnt = GetAdjacentMines(board, row, col);
18        
19        if (cnt > 0) {
20            board[row][col] = (char)(cnt + '0');
21        } else {
22            board[row][col] = 'B';
23            for (int i = 0; i < 8; i++) {
24                int x = row + dx[i], y = col + dy[i];
25                if (x >= 0 && x < board.Length && y >= 0 && y < board.First().Count() && board[x][y] == 'E') {
26                    DFS(board, x, y);
27                }
28            }
29        }
30    }
31
32    private int GetAdjacentMines(char[][] board, int row, int col) {
33        int cnt = 0;
34        for (int i = 0; i < 8; i++) {
35            int x = row + dx[i], y = col + dy[i];
36            if (x >= 0 && x < board.Length && y >= 0 && y < board.First().Count() && (board[x][y] == 'M' || board[x][y] == 'X')) {
37                cnt++;
38            }
39        }
40        return cnt;
41    }
42}

In all the solutions above, we first check if the clicked square contains mine. If yes, board is updated and returned. If not, we use DFS to reveal the squares. If a square containing 'E' has no adjacent mines, it's updated to 'B' and process is repeated for all it's unrevealed neighbors. If it has adjacent mines, it's updated to digit representing the number of such mines.## Ruby Solution

Below is the approach implemented in Ruby:

1
2ruby
3# @param {Character[][]} board
4# @param {Integer[]} click
5# @return {Character[][]}
6def update_board(board, click)
7    row, col = click
8    return board if row < 0 or row == board.size or col < 0 or col == board.first.size
9
10    if board[row][col] == "M"
11        board[row][col] = "X"
12    elsif board[row][col] == "E"
13        count = (-1..1).flat_map{|i| (-1..1).map{|j| board[row + i]&.[](col + j) == "M" ? 1 : 0}}.sum
14
15        if count == 0
16            board[row][col] = "B"
17            (-1..1).each{|i| (-1..1).each{|j| update_board(board, [row + i, col + j])}}
18        else
19            board[row][col] = count.to_s
20        end
21    end
22    board
23end

Swift Solution

Here is the Swift solution with the same DFS approach:

1
2swift
3class Solution {
4    var board = [[Character]]()
5    var dx = [0, 0, -1, 1, -1, -1, 1, 1]
6    var dy = [-1, 1, 0, 0, -1, 1, -1, 1]
7
8    func updateBoard(_ board: [[Character]], _ click: [Int]) -> [[Character]] {
9        self.board = board
10        clickHelper(click[0], click[1])
11        return self.board
12    }
13
14    func clickHelper(_ x: Int, _ y: Int) {
15        if x<0 || y<0 || x == board.count || y == board[0].count || board[x][y] != "E" && board[x][y] != "M" { return }
16        if board[x][y] == "M" {
17            board[x][y] = "X"
18            return
19        }
20
21        // check adjacent cells for mines.
22        var mines = 0
23        for direction in 0..<8 {
24            let nx = x + dx[direction]
25            let ny = y + dy[direction]
26            if nx<0 || ny<0 || nx == board.count || ny == board[0].count { continue }
27            if board[nx][ny] == "M" || board[nx][ny] == "X" { mines += 1 }
28        }
29
30        if mines > 0 {
31            // if there are mines adjacent, add that number
32            board[x][y] = Character("\(mines)")
33        } else {
34            // if there are no adjacent mines, update to B, and DFS on all adjacent cells.
35            board[x][y] = "B"
36            for direction in 0..<8 {
37                let nx = x + dx[direction]
38                let ny = y + dy[direction]
39                clickHelper(nx,ny)
40            }
41        }
42    }
43}

RUST Solution

Here is the RUST solution with the same DFS approach:

1
2rust
3impl Solution {
4    pub fn update_board(mut board: Vec<Vec<char>>, click: Vec<i32>) -> Vec<Vec<char>> {
5        let (r, c) = (click[0] as usize, click[1] as usize);
6        if board[r][c] == 'M' {
7            board[r][c] = 'X';
8            return board;
9        }
10
11        let directions = vec![
12            (-1, 0),
13            (1, 0),
14            (0, -1),
15            (0, 1),
16            (-1, -1),
17            (-1, 1),
18            (1, -1),
19            (1, 1),
20        ];
21        let (m, n) = (board.len(), board[0].len());
22
23        let mut stack = vec![(r, c)];
24        while let Some((r, c)) = stack.pop() {
25            if board[r][c] == 'E' {
26                let mut mines = 0;
27                for &(dr,dc) in directions.iter() {
28                    let (nr, nc) = (r as i32 + dr, c as i32 + dc);
29                    if nr >= 0 && nc >= 0 && (nr as usize) < m && (nc as usize) < n {
30                        if ['M', 'X'].contains(&board[nr as usize][nc as usize]) {
31                            mines += 1;
32                        }
33                    }
34                }
35
36                if mines == 0 {
37                    board[r][c] = 'B';
38                    for &(dr,dc) in directions.iter() {
39                        let (nr, nc) = (r as i32 + dr, c as i32 + dc);
40                        if nr >= 0 && nc >= 0 && (nr as usize) < m && (nc as usize) < n {
41                            stack.push((nr as usize, nc as usize));
42                        }
43                    }
44                } else {
45                    board[r][c] = std::char::from_digit(mines, 10).unwrap();
46                }
47            }
48        }
49
50        board
51    }
52}

In the solution code of each programming language, we first check if the clicked square is a mine. If it is a mine, we simply stop and change it to 'X', else we continue. We then count the number of adjacent mines-if it is greater than zero, we stop and change the square to the number of mines. If no adjacent mines are found, we call DFS on all neighboring squares.


Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ