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.
- If a mine ('M') is revealed, change it to 'X' and return the board.
- 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.
- 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.