https://leetcode-cn.com/problems/minesweeper/solution/python3-dfsbfszhu-shi-by-xxd630/
規則：
- 'M' 代表一個未挖出的地雷
- 'X' 則表示一個已挖出的地雷，
- 'E' 代表一個未挖出的空方塊，
- 'B' 代表沒有相鄰（上，下，左，右，和所有4個對角線）地雷的已挖出的空白方塊，
- 數字（'1' 到 '8'）表示有多少地雷與這塊已挖出的方塊相鄰，
邊界條件：
- 現在給出在所有未挖出的方塊中（'M'或者'E'）的下一個點擊位置（行和列索引），根據以下規則，回傳相應位置被點擊后對應的面板：
- 如果一個地雷（'M'）被挖出，游戲就結束了- 把它改為 'X'，
- 如果一個沒有相鄰地雷的空方塊（'E'）被挖出，修改它為（'B'），并且所有和其相鄰的方塊都應該被遞回地揭露，
- 如果一個至少與一個地雷相鄰的空方塊（'E'）被挖出，修改它為數字（'1'到'8'），表示相鄰地雷的數量，
- 如果在此次點擊中，若無更多方塊可被揭露，則回傳面板，
如果click是'M'，那么就是踩雷了設定為X退出，回傳棋盤，
如果不是分別進入DFS和BFS
- DFS首先設定邊界條件如果不是‘E’return，剩下的就是和200島嶼問題一樣進行DFS，只不過這里是八連通
class SolutionDFS:
def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
if not board:
return []
m,n=len(board),len(board[0])
i,j=click[0],click[1]
if board[i][j] == 'M':
board[i][j] = 'X'
return board
self.dfs(board,i,j)
return board
def dfs(self,board,i,j):
if board[i][j] != 'E':
return
m,n=len(board),len(board[0])
directions = [(-1,-1), (0,-1), (1,-1), (1,0), (1,1), (0,1), (-1,1), (-1,0)]
mine_count = 0
for d in directions:
ni,nj=i+d[0],j+d[1]
if 0<=ni<m and 0<=nj<n and board[ni][nj]=='M':
mine_count+=1
if mine_count == 0:
board[i][j] = 'B'
else:
board[i][j] = str(mine_count)
return
for d in directions:
ni,nj=i+d[0],j+d[1]
if 0 <= ni <m and 0<=nj<n:
self.dfs(board,ni,nj)
- BFS：可以當做BFS模板的思路了沒遍歷過的放到queue標記board，完成后放到visited
class SolutionBFS:
def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
m,n=len(board),len(board[0])
i,j=click[0],click[1]
if board[i][j] == "M":
board[i][j] = "X"
directions = [(-1,-1), (0,-1), (1,-1), (1,0), (1,1), (0,1), (-1,1), (-1,0)]
import collections
q = collections.deque()
q.append(click)
visited = set(click)
def numBombs(board,i,j):
mine_count = 0
for d in directions:
ni, nj = i + d[0], j + d[1]
if 0<=ni<m and 0<=nj<n and board[ni][nj] == 'M':
mine_count+=1
return mine_count
while q:
for _ in range(len(q)):
x,y=q.popleft()
if board[x][y] == 'E':
bombsNextTo = numBombs(board,x,y)
board[x][y] = "B" if bombsNextTo == 0 else str(bombsNextTo)
if bombsNextTo == 0:
for d in directions:
ni, nj = x + d[0], y + d[1]
if 0<=ni<m and 0<=nj<n and (ni,nj) not in visited:
q.append((ni,nj))
visited.add((ni,nj))
return board
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/114561.html
標籤：其他
上一篇：leetcode——二分
下一篇：陣列與鏈表的應用—陣列記憶體模型