假设我们有一个包含X和O的2D板。捕获X包围的所有区域。通过将该包围的区域中的所有O更改为X来捕获区域。
X | X | X | X |
X | Ø | Ø | X |
X | X | Ø | X |
X | Ø | X | X |
运行后输出
X | X | X | X |
X | X | X | X |
X | X | X | X |
X | Ø | X | X |
为了解决这个问题,我们将遵循以下步骤-
如果不存在板,则返回空白板
对于i,范围为0到行数– 1-
如果board [i,0] ='O',则make_one(board,i,0)
如果board [i,行长-1] ='O',则make_one(board,i,行长– 1)
对于i,范围为0到列数– 1 −
如果board [0,i] ='O',则make_one(board,0,i)
如果board [行数– 1,i] ='O',则make_one(board,行数– 1,i)
对于0到行数范围内的i
如果board [i,j] ='O',则board [i,j] ='X',否则为1,board [i,j] ='O'
对于范围从0到列数的j
make_one将像-
如果i <0或j <0或i> =行数或j> =列数或board [i,j] ='X'或board [i,j] ='1',则返回
板[i,j]:= 1
呼叫make_one(voard,i + 1,j),make_one(voard,i-1,j),make_one(voard,i,j + 1),make_one(voard,i,j-1)
让我们看下面的实现以更好地理解-
class Solution(object): def solve(self, board): if not board: return board for i in range(len(board)): if board[i][0]=='O': self.make_one(board,i,0) if board[i][len(board[0])-1] == 'O': self.make_one(board,i,len(board[0])-1) for i in range(len(board[0])): if board[0][i]=='O': self.make_one(board,0,i) if board[len(board)-1][i] == 'O': self.make_one(board,len(board)-1,i) for i in range(len(board)): for j in range(len(board[i])): if board[i][j]=='O': board[i][j]='X' elif board[i][j]=='1': board[i][j]='O' return board def make_one(self, board,i,j): if i<0 or j<0 or i>=len(board) or j>=len(board[0]) or board[i][j]=='X' or board[i] [j]=='1': return board[i][j]='1' self.make_one(board,i+1,j) self.make_one(board,i-1,j) self.make_one(board,i,j+1) self.make_one(board,i,j-1) ob1 = Solution()print(ob1.solve([["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]))
[["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
输出结果
[['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X'], ['X', 'O', 'X', 'X']]