Mind palace

some thoughts

0%

529. Minesweeper

Posted on Edited on In Disqus:
Symbols count in article: 2.3k Reading time ≈ 2 mins.

dfs

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
33
34
35
class Solution {
public:
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        m = board.size(), n = board[0].size();
        switch (board[click[0]][click[1]]) {
            case 'M': board[click[0]][click[1]] = 'X'; return board;
            case 'E': update(board, click[0], click[1]); break;
        }
        return board;
    }

    int count(const vector<vector<char>> &b, int y, int x) {
        int res = 0;
        for (int i = 0; i < 8; ++i) {
            int yy = y + dy[i], xx = x + dx[i];
            res += (0 <= yy && yy < m && 0 <= xx && xx < n && b[yy][xx] == 'M');
        }
        return res;
    }

    void update(vector<vector<char>> &b, int y, int x) {
        if (y < 0 || y >= m || x < 0 || x >= n || b[y][x] != 'E') return;
        int cnt = count(b, y, x);
        if (cnt == 0) {
            b[y][x] = 'B';
            for (int i = 0; i < 8; ++i) {
                update(b, y + dy[i], x + dx[i]);
            }
        } else {
            b[y][x] = '0' + cnt;
        }
    }

    int m, n, dy[8] = {1, 1, 0, -1, -1, -1, 0, 1}, dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
};
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
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        m = board.size(), n = board[0].size();
        switch (board[click[0]][click[1]]) {
            case 'M': {
                board[click[0]][click[1]] = 'X';
                return board;
            } break;
            case 'E': {
                update(board, click[0], click[1]);
            }
        }
        return board;
    }

    int count(const vector<vector<char>> &b, int y, int x) {
        int dy[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx[] = {0, 1, 1, 1, 0, -1, -1, -1};
        int res = 0;
        for (int i = 0; i < 8; ++i) {
            int yy = y + dy[i], xx = x + dx[i];
            if (yy < 0 || yy >= m || xx < 0 || xx >= n || b[yy][xx] != 'M') continue;
            ++res;
        }
        return res;
    }

    void update(vector<vector<char>> &b, int y, int x) {
        if (y < 0 || y >= m || x < 0 || x >= n || b[y][x] != 'E') return;
        int ret = count(b, y, x);
        int dy[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx[] = {0, 1, 1, 1, 0, -1, -1, -1};
        if (ret == 0) {
            b[y][x] = 'B';
            for (int i = 0; i < 8; ++i) {
                update(b, y + dy[i], x + dx[i]);
            }
        } else {
            b[y][x] = '0' + ret;
        }
    }

    int m, n;
};