> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/search/sao-ge/minesweeper.md).

# Minesweeper

<https://leetcode.com/problems/minesweeper/description/>

> Let's play the minesweeper game (Wikipedia, online game)!
>
> You are given a 2D char matrix representing the game board. 'M' represents an unrevealed mine, 'E' represents an unrevealed empty square, 'B' represents a revealed blank square that has no adjacent (above, below, left, right, and all 4 diagonals) mines, digit ('1' to '8') represents how many mines are adjacent to this revealed square, and finally 'X' represents a revealed mine.
>
> Now given the next click position (row and column indices) among all the unrevealed squares ('M' or 'E'), return the board after revealing this position according to the following rules:
>
> If a mine ('M') is revealed, then the game is over - change it to 'X'.
>
> If an empty square ('E') with no adjacent mines is revealed, then change it to revealed blank ('B') and all of its adjacent unrevealed squares should be revealed recursively.
>
> If an empty square ('E') with at least one adjacent mine is revealed, then change it to a digit ('1' to '8') representing the number of adjacent mines.
>
> Return the board when no more squares will be revealed.

## Thoughts

这道题的意思是如果碰到雷就立马结束。否则继续遍历，周围有雷，就把B更新为雷的数目，并不再对它后面的进行遍历， M也是。只有周围没雷的B才继续往后遍历。

## Code

```
class Solution {
public:
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        queue<pair<int, int>> q;
        auto x = click[0], y = click[1];
        if (board[x][y] == 'M') {
            board[x][y] = 'X';
        } else {
            q.emplace(x, y);
        }

        const auto m = board.size(), n = board[0].size();
        while (!q.empty()) {
            const auto size = q.size();
            for (int i = 0; i < size; ++i) {
                const auto p = q.front(); q.pop();
                int cur_x = p.first, cur_y = p.second;
                if (board[cur_x][cur_y] != 'E') continue;
                int count = 0;
                vector<pair<int, int>> tmp;
                for (int j = -1; j <= 1; ++j) {
                    for (int k = -1; k <= 1; ++k) {
                        x = cur_x + j;
                        y = cur_y + k;
                        if (x >= 0 && x < m && y >= 0 && y < n) {
                            if (board[x][y] == 'M') ++count;
                            tmp.emplace_back(x, y);
                        }
                    }
                }
                if (count) {
                    board[cur_x][cur_y] = '0' + count;
                } else {
                    board[cur_x][cur_y] = 'B';
                    for (const auto p : tmp) {
                        q.push(p);
                    }
                }
            }
        }
        return board;
    }
};
```

```
class Solution {
    public char[][] updateBoard(char[][] board, int[] click) {
        int[][] dirs = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {-1, 1}, {-1, -1}, {1, -1}, {1, 1}};
        int m = board.length, n = board[0].length;

        if (board[click[0]][click[1]] == 'M') {
            board[click[0]][click[1]] = 'X';
            return board;
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.add(click);

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] pos = queue.poll();
                char c = board[pos[0]][pos[1]];
                if (c == 'M' || c == 'B') {
                    continue;
                }

                int count = 0;
                for (int[] dir : dirs) {
                    int x = pos[0] + dir[0];
                    int y = pos[1] + dir[1];
                    if (x >= 0 && x < m && y >= 0 && y < n) {
                        char b = board[x][y];
                        if (b == 'M') {
                            count++;
                        }
                    }
                }

                if (count != 0) {
                    board[pos[0]][pos[1]] = (char)(count + '0');
                    continue;
                }

                board[pos[0]][pos[1]] = 'B';
                for (int[] dir : dirs) {
                    int x = pos[0] + dir[0];
                    int y = pos[1] + dir[1];
                    if (x >= 0 && x < m && y >= 0 && y < n) {
                        queue.add(new int[]{x, y});
                    }
                }
            }
        }

        return board;
    }
}
```

## Analysis

Errors:

1. 对于当前点, 没判断之前是否遍历过了

时空复杂度都是O(MN)