周辺地域Python

XとOを含む2Dボードがあるとします。Xで囲まれたすべての領域をキャプチャします。領域は、その囲まれた領域ですべてのOをXに変更することでキャプチャされます。

実行後、出力は次のようになります

これを解決するには、次の手順に従います-

• ボードが存在しない場合は、ブランクボードを返却してください

• 0から行数までの範囲のiの場合-1−

  • board [i、0] =‘O’の場合、make_one（board、i、0）

  • board [i、行の長さ-1] =‘O’の場合、make_one（board、i、行の長さ-1）

• 0から列数までの範囲のiの場合-1−

  • board [0、i] =‘O’の場合、make_one（board、0、i）

  • board [count of row-1、i] =‘O’の場合、make_one（board、count of row-1、i）

• 0から行数の範囲のiの場合

  • 0から列数までの範囲のjの場合

    • board [i、j] =‘O’の場合、board [i、j] =‘X’、それ以外の場合、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):
      """
      :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"]]