529. Minesweeper
Description
Intuition
- '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'.
- 'E'
- becomes 'B' with no adjacent mines is revealed, then change it to revealed blank ('B') and all of its adjacent unrevealed squares should be revealed recursively.
- a digit ('1' to '8') representing the number of adjacent mines.
Analysis
我们首先要认识到几个结论
- 一颗雷 总是被数字或者地雷包围的，进一步可以推出，如果
click在一个非雷的地方，那么其实recursively discover并不会使你触雷
所以每次BFS的时候我们可以先update mine number</p> 如果这个格子变成了数字，那么就是属于雷附近的格子，就不需要再将neighbor放进去了queue了</p> 如果是B，那么把周围unreveal empty square 放进queue