Python 中的包围区域

假设我们有一个包含 X 和 O 的二维棋盘。捕获所有被 X 包围的区域。通过将该包围区域中的所有 O 更改为 X 来捕获一个区域。

XXXX
XOOX
XXOX
XOXX

运行后输出将是

XXXX
XXXX
XXXX
XOXX

为了解决这个问题，我们将遵循以下步骤 -

  • 如果棋盘不存在，则返回空白棋盘
  • 对于 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']]

更新于: 2020-05-04

227 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告