扫雷游戏 图解题解

这道题到底在问什么

输入

点中间空格,周围正好 1 颗雷

输出

该格变数字 1,不扩散

输入

点角落空格,周围 0 颗雷

输出

该格变 B,并把邻居一片翻开

先想最直接的笨办法

先把 (0,0) 周围在界内的邻居用橙色圈出来,一个一个看是不是雷,红色的才算一颗。（动画第 8 步）

最优解：一步一步想明白

1. 3记住这把尺子:空格先数雷,有雷填数字就刹车,没雷变 B 接着冲。每一帧都在套它。
2. 4红色 M = 没挖的雷;灰色 E = 没挖的空格这是初始盘面。红色的 M 是雷,在 (1,2);其余灰色的 E 都是还没挖开的空格。我们要演两种点法。
3. 5点击落在 (1,2),翻开一看是 M先看简单的一条。假如这次点的正好是 (1,2),翻开一看是 M,一颗雷。
4. 6雷被挖出,(1,2) 改为 X碰到雷不数邻居、不扩散,直接把它改成 X,游戏立刻结束,返回盘面。这就是规则一,一步到位。
5. 7重新开一局,点击落在左上角 (0,0)重新开一局。这次点左上角 (0,0),它是空格,不是雷,于是从这里开始一次 DFS 揭开。
6. 8圈出 (0,0) 在界内的 3 个邻居,逐格找雷　|　已揭开 0先把 (0,0) 周围在界内的邻居用橙色圈出来,一个一个看是不是雷,红色的才算一颗。
7. 9看 (0,0) 的 8 个邻居,数到 0 颗雷　|　已揭开 0进入 (0,0)(紫色)。橙色圈出的是它在界内的邻居,挨个看一遍,数雷时只把标红的雷格算进去,这一格数到 0 颗雷。
8. 10(0,0) 周围 0 颗雷,改成 B　|　已揭开 1周围一颗雷都没有,于是把 (0,0) 改成 B 空白(变蓝)。空白格意味着要继续往外揭开。
9. 11(0,0) 向 3 个没挖的邻居递归揭开　|　已揭开 1(0,0) 是空白,把它周围还没挖的格 (0,1)、(1,0)、(1,1)(橙色)逐个压进递归栈,接着一个个揭开它们。
10. 12(0,1) 周围在界内共 5 格,只圈出仍未揭开的 4 个候选格/雷　|　已揭开 1(0,1) 周围在界内的格子共 5 个,屏幕只圈出仍未揭开的 4 个候选格/雷;已经揭开的 (0,0) 不是雷、不影响这次数雷计数。
11. 13看 (0,1) 的 8 个邻居,数到 1 颗雷　|　已揭开 1轮到 (0,1),同样数它周围 8 格,这一回数到 1 颗雷。
12. 14(0,1) 周围有雷,填成 1,不再扩散　|　已揭开 2周围雷数大于 0,所以 (0,1) 直接填成数字 1(变绿)。它像一道墙,挡住洪水,不再往外扩散。
13. 15看 (1,0) 的 8 个邻居,数到 0 颗雷　|　已揭开 2轮到 (1,0),同样数它周围 8 格,这一回数到 0 颗雷。
14. 16(1,0) 周围 0 颗雷,改成 B　|　已揭开 3(1,0) 周围同样没雷,也变成 B,继续向外冲。
15. 17(1,0) 向 3 个没挖的邻居递归揭开　|　已揭开 3(1,0) 是空白,把它周围还没挖的格 (1,1)、(2,0)、(2,1)(橙色)逐个压进递归栈,接着一个个揭开它们。
16. 18看 (1,1) 的 8 个邻居,数到 1 颗雷　|　已揭开 3轮到 (1,1),同样数它周围 8 格,这一回数到 1 颗雷。
17. 19(1,1) 周围有雷,填成 1,不再扩散　|　已揭开 4(1,1) 周围也有雷,填成 1 就刹车,这片墙又长出一格。
18. 20看 (2,0) 的 8 个邻居,数到 0 颗雷　|　已揭开 4轮到 (2,0),同样数它周围 8 格,这一回数到 0 颗雷。
19. 21(2,0) 周围 0 颗雷,改成 B　|　已揭开 5(2,0) 周围同样没雷,也变成 B,继续向外冲。
20. 22(2,0) 向 1 个没挖的邻居递归揭开　|　已揭开 5(2,0) 是空白,把它周围还没挖的格 (2,1)(橙色)逐个压进递归栈,接着一个个揭开它们。
21. 23看 (2,1) 的 8 个邻居,数到 1 颗雷　|　已揭开 5轮到 (2,1),同样数它周围 8 格,这一回数到 1 颗雷。
22. 24(2,1) 周围有雷,填成 1,不再扩散　|　已揭开 6(2,1) 周围也有雷,填成 1 就刹车,这片墙又长出一格。
23. 25递归栈清空,左两列已揭开,右侧被数字墙挡住DFS 全部返回。最左一列是三个 B 空白,旁边一列是三个数字 1 组成的墙,墙把右侧没必要揭开的格(含那颗雷 M)挡在外面,这就是最终返回的盘面。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

#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;
    }
};

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);
                    }
                }
            }
        }
    }
}

复杂度

面试官可能追问