Minesweeper
Medium · Graphs · Explanation and code example
Reveal Blank Regions with DFS
How it works
Clicking a mine immediately marks it X. For an unrevealed empty cell, count adjacent mines in all eight directions. Show the count when positive; otherwise mark the cell blank and recursively reveal neighboring empty cells, using the changed board as the visited marker.
Steps
- Handle a clicked mine.
- Count adjacent mines at each empty cell.
- Write its number or B; expand neighbors only from a blank cell.
Complexity
- Time: O(rows × columns).
- Space: O(rows × columns) worst-case recursion stack.
Things to watch for
- Mark a cell before expanding neighbors.
- Numbered cells stop expansion.
- Include diagonal neighbors and respect the matrix boundary.
Python code example
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
C++ code example
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 kDirs[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] : kDirs)
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] : kDirs) {
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;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.