扫雷游戏 图解题解

点一下，盘面要变成什么样

给一张 m×n 的字符盘面 board：M 是没挖出的雷，E 是没挖出的空格，另给一次点击 click。点到雷（M）就改成 X、游戏结束；点到空格（E），先数它周围 8 格有几颗雷：有雷就改成对应数字、到此打住，一颗都没有就改成 B 并把周围没挖的格接着翻开，最后返回盘面。难点全在最后半句——一格空白会牵出一连串翻开，不是点哪翻哪。

为什么不能只把点中那格翻开

先只翻点中那一格看差在哪。若点到的空格周围没有雷，它要变 B，而 B 就意味着『邻格还得继续翻』，其中周围无雷的又会变 B、再往外带。只翻一格就停，等于把该展开的一大片安全区留在原地，盘面是错的。所以这题不是做一次判断，而是从点击点出发沿『无雷空格』一路蔓延，直到撞上贴着雷的格才收边——这种扎进去、走不通再退回来的遍历，就是深度优先搜索（DFS）。

空格的两条岔路，为什么只有 0 才扩散

把揭开一个空格拆成一把尺子：先数它周围 8 格（含 4 条对角线）的雷数 cnt。cnt 大于 0，说明紧挨着雷，填上 cnt 就停手——它是一道警戒线，再往外翻就踩进雷区。cnt 等于 0，周围一圈都安全，才标成 B、对没挖的邻格递归揭开。为什么偏偏 0 才扩散？因为数字格本身就在说『旁边有雷、别往这走』，点一下摊开一大片的边界，就是这些数字格圈出来的。

一次递归揭开，具体是怎么铺的

揭开某格 (i,j)，用双层循环扫 x 从 i-1 到 i+1、y 从 j-1 到 j+1 这 9 个位置，每个先判越界（0≤x＜m 且 0≤y＜n），在界内且是 M 才计入 cnt。若 cnt 为 0，这圈里还没挖的空格（E）就递归揭开。循环也会扫到 (i,j) 自己，但它此刻是待处理的 E、不是 M，不会被误当雷，省了跳过自身的判断。一格一旦标成 B 或数字就不再是 E，不会二次揭开，递归也不打转。

拿一张 3×4 盘面点 (0,0) 走一遍

盘面 3 行 4 列，唯一的雷 M 在 (1,2)，其余全是 E，点左上角 (0,0)。(0,0) 周围 (0,1)、(1,0)、(1,1) 都没雷，cnt=0，标 B 并把这三格排进递归。揭 (0,1)：周围含 (1,2)，数到 1 颗雷，填 1 停下。揭 (1,0)：无雷变 B，带出 (1,1)、(2,0)、(2,1)；(1,1) 挨着雷填 1，(2,0) 无雷变 B 又带出 (2,1)，(2,1) 挨着雷填 1。最终最左一列是三个 B，紧邻一列三个 1，把那颗雷挡在右侧，共翻开 6 格。

复杂度，还有几处一漏就全盘皆错

每个格子最多被揭开一次，数周围 8 格是常数工作，时间 O(m·n)；空间耗在递归栈，最坏整片盘面连成一块空白，栈深逼近格子总数，也是 O(m·n)。让结果全错的常是几处细节。空格不先数雷就变 B 往外扩，本该拦住洪水的数字墙没长出来，会冲穿整盘。数雷只顾上下左右 4 格漏了对角线，斜角的雷被算少，可相邻是含对角的 8 格。给填了数字的格再递归就越过警戒线，右侧不该翻的格也翻了。两种极端反而简单：空格周围无雷直接变 B，点下去是雷则一步改 X。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
        def dfs(i: int, j: int):
            cnt = 0
            for x in range(i - 1, i + 2):
                for y in range(j - 1, j + 2):
                    if 0 <= x < m and 0 <= y < n and board[x][y] == "M":
                        cnt += 1
            if cnt:
                board[i][j] = str(cnt)
            else:
                board[i][j] = "B"
                for x in range(i - 1, i + 2):
                    for y in range(j - 1, j + 2):
                        if 0 <= x < m and 0 <= y < n and board[x][y] == "E":
                            dfs(x, y)

        m, n = len(board), len(board[0])
        i, j = click
        if board[i][j] == "M":
            board[i][j] = "X"
        else:
            dfs(i, j)
        return board

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        int m = board.size(), n = board[0].size();
        int i = click[0], j = click[1];

        function<void(int, int)> dfs = [&](int i, int j) {
            int cnt = 0;
            for (int x = i - 1; x <= i + 1; ++x) {
                for (int y = j - 1; y <= j + 1; ++y) {
                    if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M') {
                        ++cnt;
                    }
                }
            }
            if (cnt) {
                board[i][j] = cnt + '0';
            } else {
                board[i][j] = 'B';
                for (int x = i - 1; x <= i + 1; ++x) {
                    for (int y = j - 1; y <= j + 1; ++y) {
                        if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E') {
                            dfs(x, y);
                        }
                    }
                }
            }
        };

        if (board[i][j] == 'M') {
            board[i][j] = 'X';
        } else {
            dfs(i, j);
        }
        return board;
    }
};

Java

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private char[][] board;
    private int m;
    private int n;

    public char[][] updateBoard(char[][] board, int[] click) {
        m = board.length;
        n = board[0].length;
        this.board = board;
        int i = click[0], j = click[1];
        if (board[i][j] == 'M') {
            board[i][j] = 'X';
        } else {
            dfs(i, j);
        }
        return board;
    }

    private void dfs(int i, int j) {
        int cnt = 0;
        for (int x = i - 1; x <= i + 1; ++x) {
            for (int y = j - 1; y <= j + 1; ++y) {
                if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M') {
                    ++cnt;
                }
            }
        }
        if (cnt > 0) {
            board[i][j] = (char) (cnt + '0');
        } else {
            board[i][j] = 'B';
            for (int x = i - 1; x <= i + 1; ++x) {
                for (int y = j - 1; y <= j + 1; ++y) {
                    if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E') {
                        dfs(x, y);
                    }
                }
            }
        }
    }
}