0529. Minesweeper
=================
题目信息
--------
:题号: 0529
:难度: Medium
:主题: 矩阵、扫雷规则、八邻域、递归揭示
:原题: `LeetCode 0529 `_
:重点: 点击地雷改为 X、空格按八邻域地雷数更新、零相邻地雷时继续揭示周围未揭示空格
题目重述
--------
给定一个扫雷棋盘 ``board`` 和一次点击坐标 ``click``。未揭示地雷用 ``'M'`` 表示,未揭示空格用 ``'E'`` 表示。按照扫雷规则更新棋盘并返回更新后的矩阵。
若点击到地雷,把该格改为 ``'X'`` 并结束。若点击到空格,统计它周围八个方向内的地雷数量:数量大于零时把该格改为对应字符 ``'1'`` 到 ``'8'``;数量为零时把它改为 ``'B'``,并继续揭示所有相邻的未揭示空格。已经揭示的格子不重复处理。
自建示例
--------
点击有相邻地雷的空格:
.. code-block:: text
输入:board = [["M","E","E"],["E","E","E"],["E","E","E"]],click = [1,1]
输出:[["M","E","E"],["E","1","E"],["E","E","E"]]
解释:中心格的八邻域中有左上角一颗地雷,因此只把中心格标记为 1,不继续展开。
直接点击地雷:
.. code-block:: text
输入:board = [["E","M"]],click = [0,1]
输出:[["E","X"]]
解释:点击位置是地雷,立即改为 X。
递归揭示零邻雷区域
------------------
点击地雷时直接改为 ``X``。点击未揭示空格后,先统计八个方向的 ``M``;若数量非零,只写入数字并停止扩展;若数量为零,写入 ``B`` 后递归访问八邻域的未揭示空格。先把当前格改写为 ``B``,就能防止递归环路和重复处理。
C++ 实现
--------
.. code-block:: cpp
class Solution {
const int directions[8][2] = {
{-1, -1}, {-1, 0}, {-1, 1}, {0, -1},
{0, 1}, {1, -1}, {1, 0}, {1, 1}
};
void reveal(std::vector>& board,
int row, int column) {
int rows = static_cast(board.size());
int columns = static_cast(board[0].size());
if (row < 0 || row >= rows || column < 0 || column >= columns ||
board[row][column] != 'E') return;
int mines = 0;
for (const auto& direction : directions) {
int nextRow = row + direction[0];
int nextColumn = column + direction[1];
if (nextRow >= 0 && nextRow < rows &&
nextColumn >= 0 && nextColumn < columns &&
board[nextRow][nextColumn] == 'M') {
++mines;
}
}
if (mines > 0) {
board[row][column] = static_cast('0' + mines);
return;
}
board[row][column] = 'B';
for (const auto& direction : directions) {
reveal(board, row + direction[0],
column + direction[1]);
}
}
public:
std::vector> updateBoard(
std::vector>& board,
std::vector& click) {
int row = click[0];
int column = click[1];
if (board[row][column] == 'M') {
board[row][column] = 'X';
} else {
reveal(board, row, column);
}
return board;
}
};
代码分析
--------
每个空格在第一次进入时就被改为 ``B`` 或数字,后续邻居不会再次展开它;八方向计数与扫雷规则完全对应。每个格子最多处理一次,时间复杂度为 ``O(rows * columns)``,递归栈空间为 ``O(rows * columns)`` 的最坏上界。