529. Minesweeper LeetCode Solution
In this guide, you will get 529. Minesweeper LeetCode Solution with the best time and space complexity. The solution to Minesweeper problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Minesweeper solution in C++
- Minesweeper solution in Java
- Minesweeper solution in Python
- Additional Resources
Problem Statement of Minesweeper
Let’s play the minesweeper game (Wikipedia, online game)!
You are given an m x n char matrix board representing the game board where:
‘M’ represents an unrevealed mine,
‘E’ represents an unrevealed empty square,
‘B’ represents a revealed blank square that has no adjacent mines (i.e., above, below, left, right, and all 4 diagonals),
digit (‘1’ to ‘8’) represents how many mines are adjacent to this revealed square, and
‘X’ represents a revealed mine.
You are also given an integer array click where click = [clickr, clickc] represents the next click position among all the unrevealed squares (‘M’ or ‘E’).
Return the board after revealing this position according to the following rules:
If a mine ‘M’ is revealed, then the game is over. You should change it to ‘X’.
If an empty square ‘E’ with no adjacent mines is revealed, then change it to a revealed blank ‘B’ and all of its adjacent unrevealed squares should be revealed recursively.
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.
Return the board when no more squares will be revealed.
Example 1:
Input: board = [[“E”,”E”,”E”,”E”,”E”],[“E”,”E”,”M”,”E”,”E”],[“E”,”E”,”E”,”E”,”E”],[“E”,”E”,”E”,”E”,”E”]], click = [3,0]
Output: [[“B”,”1″,”E”,”1″,”B”],[“B”,”1″,”M”,”1″,”B”],[“B”,”1″,”1″,”1″,”B”],[“B”,”B”,”B”,”B”,”B”]]
Example 2:
Input: board = [[“B”,”1″,”E”,”1″,”B”],[“B”,”1″,”M”,”1″,”B”],[“B”,”1″,”1″,”1″,”B”],[“B”,”B”,”B”,”B”,”B”]], click = [1,2]
Output: [[“B”,”1″,”E”,”1″,”B”],[“B”,”1″,”X”,”1″,”B”],[“B”,”1″,”1″,”1″,”B”],[“B”,”B”,”B”,”B”,”B”]]
Constraints:
m == board.length
n == board[i].length
1 <= m, n <= 50
board[i][j] is either ‘M’, ‘E’, ‘B’, or a digit from ‘1’ to ‘8’.
click.length == 2
0 <= clickr < m
0 <= clickc < n
board[clickr][clickc] is either ‘M’ or ‘E’.
Complexity Analysis
- Time Complexity: O(mn)
- Space Complexity: O(mn)
529. Minesweeper LeetCode Solution in C++
class Solution {
public:
vector<vector<char>> updateBoard(vector<vector<char>>& board,
vector<int>& click) {
const int i = click[0];
const int j = click[1];
if (board[i][j] == 'M') {
board[i][j] = 'X';
return board;
}
dfs(board, i, j);
return board;
}
private:
static constexpr int dirs[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1},
{0, 1}, {1, -1}, {1, 0}, {1, 1}};
void dfs(vector<vector<char>>& board, int i, int j) {
if (i < 0 || i == board.size() || j < 0 || j == board[0].size())
return;
if (board[i][j] != 'E')
return;
const int minesCount = getMinesCount(board, i, j);
board[i][j] = minesCount == 0 ? 'B' : '0' + minesCount;
if (minesCount == 0)
for (const auto& [dx, dy] : dirs)
dfs(board, i + dx, j + dy);
}
int getMinesCount(const vector<vector<char>>& board, int i, int j) {
int minesCount = 0;
for (const auto& [dx, dy] : dirs) {
const int x = i + dx;
const int y = j + dy;
if (x < 0 || x == board.size() || y < 0 || y == board[0].size())
continue;
if (board[x][y] == 'M')
++minesCount;
}
return minesCount;
}
};
/* code provided by PROGIEZ */529. Minesweeper LeetCode Solution in Java
class Solution {
public char[][] updateBoard(char[][] board, int[] click) {
final int i = click[0];
final int j = click[1];
if (board[i][j] == 'M') {
board[i][j] = 'X';
return board;
}
dfs(board, i, j);
return board;
}
private static final int[][] dirs = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1},
{0, 1}, {1, -1}, {1, 0}, {1, 1}};
private void dfs(char[][] board, int i, int j) {
if (i < 0 || i == board.length || j < 0 || j == board[0].length)
return;
if (board[i][j] != 'E')
return;
final int minesCount = getMinesCount(board, i, j);
board[i][j] = minesCount == 0 ? 'B' : (char) ('0' + minesCount);
if (minesCount == 0)
for (int[] dir : dirs)
dfs(board, i + dir[0], j + dir[1]);
}
private int getMinesCount(char[][] board, int i, int j) {
int minesCount = 0;
for (final int[] dir : dirs) {
final int x = i + dir[0];
final int y = j + dir[1];
if (x < 0 || x == board.length || y < 0 || y == board[0].length)
continue;
if (board[x][y] == 'M')
++minesCount;
}
return minesCount;
}
}
// code provided by PROGIEZ529. Minesweeper LeetCode Solution in Python
class Solution:
def updateBoard(self, board: list[list[str]],
click: list[int]) -> list[list[str]]:
i, j = click
if board[i][j] == 'M':
board[i][j] = 'X'
return board
dirs = ((-1, -1), (-1, 0), (-1, 1), (0, -1),
(0, 1), (1, -1), (1, 0), (1, 1))
def getMinesCount(i: int, j: int) -> int:
minesCount = 0
for dx, dy in dirs:
x = i + dx
y = j + dy
if x < 0 or x == len(board) or y < 0 or y == len(board[0]):
continue
if board[x][y] == 'M':
minesCount += 1
return minesCount
def dfs(i: int, j: int) -> None:
if i < 0 or i == len(board) or j < 0 or j == len(board[0]):
return
if board[i][j] != 'E':
return
minesCount = getMinesCount(i, j)
board[i][j] = 'B' if minesCount == 0 else str(minesCount)
if minesCount == 0:
for dx, dy in dirs:
dfs(i + dx, j + dy)
dfs(i, j)
return board
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.