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 unrevealedsquares 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.
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:
- The range of the input matrix's height and width is [1,50].
- The click position will only be an unrevealed square ('M' or 'E'), which also means the input board contains at least one clickable square.
- The input board won't be a stage when game is over (some mines have been revealed).
- 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.
這個是掃雷游戲,需要注意上面的四條規(guī)則失球，可以用DFS求解，在給定的位置上點擊時，如果點到了地雷携丁，那就改為‘X’，直接返回整個數(shù)組就行支鸡，如果沒有點到地雷剧蚣，根據(jù)上述的規(guī)則改相應(yīng)的字母。還有吗货，如果附近有地雷泳唠，那就根據(jù)周圍地雷的數(shù)量，把自己的位置改為這個數(shù)字的str類型就行宙搬，并且在周圍沒有地雷的位置上繼續(xù)遞歸笨腥，直到?jīng)]有更多的點被揭露，返回整個方塊勇垛。
注意:
- 在Example 1中脖母，在（0,3）位置上之所有沒有揭露，那是因為它的線面有地雷闲孤，左右邊是有'1'谆级，而且這個'1'所在的方塊中，是不能繼續(xù)遞歸下去的讼积。所以最后（0,3）這個位置沒有被揭露了肥照。所以DFS就油然而生了。
- 這個方向是有八個方向的勤众。
python3代碼：
class Solution:
def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
lenr, lenc = len(board), len(board[0])
if lenr == 0 or lenc == 0:
return board
sr, sc = click[0], click[1]
if board[sr][sc] == 'M':
board[sr][sc] = 'X'
return board
visited = [[0 for i in range(lenc + 1)] for j in range(lenr + 1)]
dx = [1, 1, -1, -1, 0, 0, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
def dfs(r, c):
if board[r][c] == 'M' or visited[r][c] == 1:
return
visited[r][c] = 1
num_mine = 0
for i in range(8):
x = r + dx[i]
y = c + dy[i]
if 0 <= x < lenr and 0 <= y < lenc and board[x][y] == 'M':
num_mine += 1
if num_mine > 0:
board[r][c] = str(num_mine)
else:
board[r][c] = 'B'
for i in range(8):
x = r + dx[i]
y = c + dy[i]
if 0 <= x < lenr and 0 <= y < lenc and visited[x][y] == 0:
dfs(x, y)
dfs(sr, sc)
return board
