from typing import List
# 這道題的思路是從矩陣的四周開始尋找，如果這個字符為O，就向上下左右遞回，
# 先將找到的O轉化為其他字符，最后將沒有找到的O轉化為X，將找到的O不變
class Solution:
def solve(self, board: List[List[str]]) -> None:
# 如果串列為慷訓者串列中為空，回傳空
if not board or not board[0] :return
# 定義行和列
row,col = len(board),len(board[0])
# 定義遞回函式
def dfs(index1, index2):
# 首先將進來的轉化為其他字符
board[index1][index2] = "B"
# 然后上下左右遞回
for x, y in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
# 注意這里不能直接在index1上邊相加減
i = index1 + x
j = index2 + y
# 注意這里一定是從1開始的，否則就是錯誤的，
if 1 <= i < row and 1 <= j < col and board[i][j] == "O":
dfs(i,j)
# 尋找第一列和最后一列
for i in range(row):
if board[i][0] == "O":
dfs(i,0)
if board[i][col - 1] == "O":
dfs(i,col - 1)
# 尋找第一行和最后一行
for i in range(col):
if board[0][i] == "O":
dfs(0,i)
if board[row - 1][i] == "O":
dfs(row - 1,i)
# 將字符恢復原位，
for i in range(row):
for j in range(col):
if board[i][j] == "O":
board[i][j] = "X"
if board[i][j] == "B":
board[i][j] = "O"
A = Solution()
A.solve([["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]])
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/56986.html
標籤：Python