​LeetCode刷题实战529:扫雷游戏

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 扫雷游戏,我们先来看题面:
https://leetcode-cn.com/problems/minesweeper/

​LeetCode刷题实战529:扫雷游戏

​LeetCode刷题实战529:扫雷游戏

示例                         

​LeetCode刷题实战529:扫雷游戏

解题


​LeetCode刷题实战529:扫雷游戏

代码如下:

class Solution {
public:
    int dir_x[8] = {0, 1, 0, -1, 1, 1, -1, -1};
    int dir_y[8] = {1, 0, -1, 0, 1, -1, 1, -1};
 
    void dfs(vector<vector<char>>& board, int x, int y) {
        int cnt = 0;
        for (int i = 0; i < 8; ++i) {
            int tx = x + dir_x[i];
            int ty = y + dir_y[i];
            if (tx < 0 || tx >= board.size() || ty < 0 || ty >= board[0].size()) {
                continue;
            }
            // 不用判断 M,因为如果有 M 的话游戏已经结束了
            cnt += board[tx][ty] == 'M';
        }
        if (cnt > 0) {
            // 规则 3
            board[x][y] = cnt + '0';
        } else {
            // 规则 2
            board[x][y] = 'B';
            for (int i = 0; i < 8; ++i) {
                int tx = x + dir_x[i];
                int ty = y + dir_y[i];
                // 这里不需要在存在 B 的时候继续扩展,因为 B 之前被点击的时候已经被扩展过了
                if (tx < 0 || tx >= board.size() || ty < 0 || ty >= board[0].size() || board[tx][ty] != 'E') {
                    continue;
                }
                dfs(board, tx, ty);
            }
        }
    }
 
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        int x = click[0], y = click[1];
        if (board[x][y] == 'M') {
            // 规则 1
            board[x][y] = 'X';
        } else {
            dfs(board, x, y);
        }
        return board;
    }
};


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:

LeetCode1-520题汇总,希望对你有点帮助!
LeetCode刷题实战521:最长特殊序列 Ⅰ
LeetCode刷题实战522:最长特殊序列 II
LeetCode刷题实战523:连续的子数组和
LeetCode刷题实战524:通过删除字母匹配到字典里最长单词
LeetCode刷题实战525:连续数组
LeetCode刷题实战526:优美的排列
LeetCode刷题实战527:单词缩写
LeetCode刷题实战528:按权重随机选择

​LeetCode刷题实战529:扫雷游戏

本篇文章来源于微信公众号:程序IT圈

原创文章,作者:栈长,如若转载,请注明出处:https://www.cxyquan.com/19675.html

发表评论

登录后才能评论

联系我们

400-800-8888

在线咨询:点击这里给我发消息

邮件:admin@example.com

工作时间:周一至周五,9:30-18:30,节假日休息