周边地区Python

假设我们有一个包含X和O的2D板。捕获X包围的所有区域。通过将该包围的区域中的所有O更改为X来捕获区域。

XXXX
XØØX
XXØX
XØXX

运行后输出

XXXX
XXXX
XXXX
XØXX

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

  • 如果不存在板,则返回空白板

  • 对于范围从0到行数的i-1-

    • 如果board [i,0] ='O',则make_one(board,i,0)

    • 如果board [i,行长-1] ='O',则make_one(board,i,行长-1)

  • 对于i在0到cols数量的范围内-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):
      """
      :type board: List[List[str]]
      :rtype: None Do not return anything, modify board in-place instead.
      """
      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'
   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)

输入项

[["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"]]