扫雷游戏

发表于
本文字数： 1.5k 阅读时长 ≈ 1 分钟

LeetCode每日一题，529. Minesweeper

先看题目描述

大意就是一个扫雷游戏，矩阵表示扫雷游戏的板子，E 表示未翻开的空格，M 表示未翻开的雷，B 表示该格周围没有地雷，数字表示该格周围有几颗雷，X 表示这是翻开的雷，当翻到地雷时，游戏也就结束了，还有个特殊的规则是当翻开的格子周围没地雷时，所有和它相邻的方块都应该递归的暴露出来

算法和思路

由题意就可以想到，这题应该用 dfs深度优先搜索，扩散性的将各格子揭露出来，我们用代码模拟扩散的过程即可，当翻开一个格子时，若是 M，则将其变为 X，然后直接结束；否则就计算其周围格子中地雷数目，若 > 0，就改为数字；若 = 0，就改为 B，然后用同样策略递归的揭露其周围还未被翻开的格子

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    int[] dx = {0, 0, 1, -1, 1, 1, -1, -1};
    int[] dy = {1, -1, 0, 0, 1, -1, 1, -1};

    public char[][] updateBoard(char[][] board, int[] click) {
        int x = click[0];
        int y = click[1];
        if (board[x][y] == 'M') board[x][y] = 'X';
        else dfs(board, x, y);
        return board;
    }

    public void dfs(char[][] board, int x, int y) {
        int cnt = 0;
        for (int i = 0; i < 8; i++) {
            int tx = x + dx[i];
            int ty = y + dy[i];
            if (tx < 0 || tx >= board.length || ty < 0 || ty >= board[0].length) continue;
            if (board[tx][ty] == 'M') cnt++;
        }
        if (cnt > 0 ) board[x][y] = (char)(cnt + '0');
        else {
            board[x][y] = 'B';
            for (int i = 0; i < 8; i++) {
                int tx = x + dx[i];
                int ty = y + dy[i];
                if (tx < 0 || tx >= board.length || ty < 0 || ty >= board[0].length || board[tx][ty] != 'E') continue;
                dfs(board, tx, ty);
            }
        }
    }
}