Leetcode529. DFS之應用（三）：解決掃雷遊戲

Leetcode529. Minesweeper

題目

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:

1. If a mine (‘M’) is revealed, then the game is over - change it to ‘X’.

2. 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.

3. 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.

4. Return the board when no more squares will be revealed.

Example 1:

Input:

[[‘E’, ‘E’, ‘E’, ‘E’, ‘E’],

[‘E’, ‘E’, ‘M’, ‘E’, ‘E’],

[‘E’, ‘E’, ‘E’, ‘E’, ‘E’],

[‘E’, ‘E’, ‘E’, ‘E’, ‘E’]]

Click : [3,0]

Output:

[[‘B’, ‘1’, ‘E’, ‘1’, ‘B’],

[‘B’, ‘1’, ‘M’, ‘1’, ‘B’],

[‘B’, ‘1’, ‘1’, ‘1’, ‘B’],

[‘B’, ‘B’, ‘B’, ‘B’, ‘B’]]

Explanation:

Example 2:

Input:

[[‘B’, ‘1’, ‘E’, ‘1’, ‘B’],

[‘B’, ‘1’, ‘M’, ‘1’, ‘B’],

[‘B’, ‘1’, ‘1’, ‘1’, ‘B’],

[‘B’, ‘B’, ‘B’, ‘B’, ‘B’]]

Click : [1,2]

Output:

[[‘B’, ‘1’, ‘E’, ‘1’, ‘B’],

[‘B’, ‘1’, ‘X’, ‘1’, ‘B’],

[‘B’, ‘1’, ‘1’, ‘1’, ‘B’],

[‘B’, ‘B’, ‘B’, ‘B’, ‘B’]]

Explanation:

Note:

1. The range of the input matrix’s height and width is [1,50].

2. The click position will only be an unrevealed square (‘M’ or ‘E’), which also means the input board contains at least one clickable square.

3. The input board won’t be a stage when game is over (some mines have been revealed).

4. For simplicity, not mentioned rules should be ignored in this problem. For example, you don’t need to reveal all the unrevealed mines when the game is over, consider any cases that you will win the game or flag any squares.

解題分析

看到這道題，千萬不要被題目吓到了，其實這道掃雷遊戲的題目并沒有想象中的那麼難，思路還算是比較直接清晰的。

首先根據題目的要求，我們知道初始情況下，地圖隻有兩類可點選的位置，一類是地雷，一類是空位置。點選地雷的情況非常簡單，直接将地雷對應的位置M改成X輸出即可。點選空位置的情況就稍微複雜一些：一種情況是E變為B，一種情況是E變為周圍地雷的個數，一種情況是保持不變。下面我們來分别分析這三種情況。

通過上面的例子我們不難分析出：首先對周遊的每個位置将其周邊的位置進行周遊，如果周圍的位置有地雷，就将該位置的E替換為周圍地雷的個數。如果周圍的位置沒有地雷，就将E替換為B，并繼續周遊其周圍為E的位置，直到沒有位置可以再暴露出來了，這樣最後周遊完的結果就是最終輸出的結果了。

源代碼

class Solution {
public:
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        int height = board.size(), width = board[].size(), row = click[], col = click[];
        if (board[row][col] == 'M') {
            board[row][col] = 'X';
        }
        else {
            int count = ;
            for (int i = -; i <= ; i++) {
                for (int j = -; j <= ; j++) {
                    if (i ==  && j == ) {
                        continue;
                    }
                    int r = row + i, c = col + j;
                    if (r <  || r >= height || c <  || c >= width) {
                        continue;
                    }
                    if (board[r][c] == 'M') {
                        count++;
                    }
                }
            }
            if (count > ) {
                board[row][col] = count + '0';
            }
            else {
                board[row][col] = 'B';
                for (int i = -; i <= ; i++) {
                    for (int j = -; j <= ; j++) {
                        if (i ==  && j == ) {
                            continue;
                        }
                        int r = row + i, c = col + j;
                        if (r <  || r >= height || c <  || c >= width) {
                            continue;
                        }
                        if (board[r][c] == 'E') {
                            vector<int> v;
                            v.push_back(r);
                            v.push_back(c);
                            updateBoard(board, v);
                        }
                    }
                }
            }
        }
        return board;
    }
};
           

以上是我對這道問題的一些想法，有問題還請在評論區讨論留言~