leetcode: 529. Minesweeper Game

529. 扫雷游戏

来源：力扣（LeetCode）

链接: https://leetcode.cn/problems/number-of-islands/

让我们一起来玩扫雷游戏！

给你一个大小为 m x n 二维字符矩阵 board ,表示扫雷游戏的盘面,其中：

• 'M' 代表一个 未挖出的 地雷,
• 'E' 代表一个 未挖出的 空方块,
• 'B' 代表没有相邻（上,下,左,右,和所有4个对角线）地雷的 已挖出的 空白方块,
• 数字（‘1’ 到 ‘8’）表示有多少地雷与这块 已挖出的 方块相邻,
• 'X' 则表示一个 已挖出的 地雷.

给你一个整数数组 click ,其中 click = [clickr, clickc] 表示在所有 未挖出的 方块（‘M’ 或者 ‘E’）中的下一个点击位置（clickr 是行下标,clickc 是列下标）.

根据以下规则,返回相应位置被点击后对应的盘面：

• 如果一个地雷（'M'）被挖出,游戏就结束了- 把它改为'X' .
• 如果一个 没有相邻地雷 的空方块（'E'）被挖出,修改它为（'B'）,并且所有和其相邻的 未挖出 方块都应该被递归地揭露.
• 如果一个 至少与一个地雷相邻 的空方块（‘E’）被挖出,修改它为数字（‘1’ 到 ‘8’ ）,表示相邻地雷的数量.
• 如果在此次点击中,若无更多方块可被揭露,则返回盘面.

示例 1：

输入：board = [["E","E","E","E","E"],["E","E","M","E","E"],["E","E","E","E","E"],["E","E","E","E","E"]], click = [3,0]
输出：[["B","1","E","1","B"],["B","1","M","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]]

示例 2：

输入：board = [["B","1","E","1","B"],["B","1","M","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]], click = [1,2]
输出：[["B","1","E","1","B"],["B","1","X","1","B"],["B","1","1","1","B"],["B","B","B","B","B"]]

提示：

• m == board.length
• n == board[i].length
• 1 <= m, n <= 50
• board[i][j] 为 'M'、'E'、'B' 或数字 '1' 到 '8' 中的一个
• click.length == 2
• 0 <= clickr < m
• 0 <= clickc < n
• board[clickr][clickc] 为 'M' 或 'E'

解法

总的思想是进行遍历,Click to start from the very beginning,Then see what it is,然后看其八个方向,这里是八个方向,Not traversing in four directions,Then count the number of landmines,If the number of mines is not after the traversal is completed0,Then change the position there to correspondcountnumber of characters,如果为0,in eight directions

• BFS：用队列进行存储该陆地,And traverse in eight directions,If the follow-up is not for the location of the mine,进入队列,直到队列为空
• DFS： Traverse in eight directions recursively

代码实现

BFS

python实现

class Solution:
    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
        r, c = click
        if board[r][c] == 'M':
            board[r][c] = 'X'
            return board
        
        rows = len(board)
        cols = len(board[0])

        visited = [[False] * cols for _ in range(rows)]
        visited[r][c] = True
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, -1), (-1, 1)]
        q = [(r, c)]
        while q:
            r, c = q.pop(0)
            count = 0
            for dr, dc in directions:
                nr = r + dr
                nc = c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    if board[nr][nc] == 'M':
                        count += 1
            
            if count > 0:
                board[r][c] = str(count)
            else:
                board[r][c] = 'B'
                for dr, dc in directions:
                    nr = r + dr
                    nc = c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and not visited[nr][nc] and board[nr][nc] == 'E':
                        q.append((nr, nc))
                        visited[nr][nc] = True
        return board

c++实现

class Solution {
    
public:
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
    
        int r = click[0], c = click[1];
        if (board[r][c] == 'M') {
    
            board[r][c] = 'X';
            return board;
        }

        int rows = board.size();
        int cols = board[0].size();
        vector<pair<int, int>> directions = {
    {
    0, 1}, {
    0, -1}, {
    1, 0}, {
    -1, 0}, {
    1, 1}, {
    1, -1}, {
    -1, 1}, {
    -1, -1}};
        vector<vector<int>> visited(rows, vector<int>(board[0].size(), 0));
        queue<pair<int, int>> q;
        q.push({
    r, c});
        while (q.size() != 0) {
    
            int count = 0;
            auto tmp = q.front();
            q.pop();
            int r = tmp.first;
            int c = tmp.second;
            for (auto dr: directions) {
    
                int nr = r + dr.first;
                int nc = c + dr.second;
                if (0 <= nr && nr < rows && 0 <= nc && nc < cols) {
    
                    if (board[nr][nc] == 'M')
                        count++;
                }
            }
            if (count > 0) 
                board[r][c] = count + '0';
            else {
    
                board[r][c] = 'B';
                for (auto dr: directions) {
    
                    int nr = r + dr.first;
                    int nc = c + dr.second;
                    if (0 <= nr  && nr < rows && 0 <= nc && nc < cols && !visited[nr][nc] && board[nr][nc] == 'E') {
    
                        q.push({
    nr, nc});
                        visited[nr][nc] = true;
                    }
                }
            }
        }
        return board;
    }
};

复杂度分析

• 时间复杂度： $O(MN)$ M和N分别为行数和列数
• 空间复杂度： $O(MN)$ M和N分别为行数和列数

DFS

python实现

class Solution:
    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
        r, c = click
        if board[r][c] == 'M':
            board[r][c] = 'X'
            return board
        
        rows = len(board)
        cols = len(board[0])

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        def dfs(r, c):
            count = 0
            for dx, dy in directions:
                nr = r + dx
                nc = c + dy
                if 0 <= nr < rows and 0 <= nc < cols:
                    if board[nr][nc] == 'M':
                        count += 1
            
            if count > 0:
                board[r][c] = str(count)
            else:
                board[r][c] = 'B'
                for dx, dy in directions:
                    nr = r + dx
                    nc = c + dy
                    if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == 'E':
                        dfs(nr, nc)
        dfs(r, c)
        return board

c++实现

class Solution {
    
    vector<pair<int, int>> directions = {
    
        {
    1, 0}, {
    -1, 0}, {
    0, 1}, {
    0, -1}, {
    1, 1}, {
    1, -1}, {
    -1, 1}, {
    -1, -1}};

public:
    void dfs(int r, int c, vector<vector<char>>& board, int rows, int cols) {
    
        int count = 0;
        for(auto tmp: directions) {
    
            int nr = r + tmp.first;
            int nc = c + tmp.second;
            if (0 <= nr && nr < rows && 0 <= nc && nc < cols) {
    
                if (board[nr][nc] == 'M')
                    count++;
            }
        }
        if (count > 0)
            board[r][c] = count + '0';
        else{
    
            board[r][c] = 'B';
            for (auto tmp: directions) {
    
                int nr = r + tmp.first;
                int nc = c + tmp.second;
                if (0 <= nr && nr < rows && 0 <= nc && nc < cols && board[nr][nc] == 'E') {
    
                    dfs(nr, nc, board, rows, cols);
            }
        }
    }
    }

    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
    
        int r = click[0], c = click[1];
        if (board[r][c] == 'M') {
    
            board[r][c] = 'X';
            return board;
        }

        int rows = board.size();
        int cols = board[0].size();
        dfs(r, c, board, rows, cols);
        return board;
    }
};

复杂度分析

• 时间复杂度： $O(MN)$ M和N分别为行数和列数
• 空间复杂度： $O(MN)$ M和N分别为行数和列数

参考

• https://leetcode.cn/problems/minesweeper/solution/sao-lei-you-xi-by-leetcode-solution/