Python 中的包圍區域

假設我們有一個包含 X 和 O 的二維棋盤。捕獲所有被 X 包圍的區域。透過將該包圍區域中的所有 O 更改為 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)
• 對於 i 從 0 到行數
  • 對於 j 從 0 到列數
    • 如果 board[i, j] = ‘O’，則 board[i, j] = ‘X’，否則對於 1，board[i, j] = ‘O’
• make_one 將類似於 -
• 如果 i < 0 或 j < 0 或 i >= 行數 或 j >= 列數 或 board[i, j] = ‘X’ 或 board[i, j] = ‘1’，則返回
• board[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']]

Arnab Chakraborty

更新於: 2020-05-04

227 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

開始學習