Python vùng xung quanh

Giả sử chúng ta có một bảng 2D chứa X và O. Chụp tất cả các vùng được bao quanh bởi X. Một vùng được ghi lại bằng cách thay đổi tất cả Os thành X trong vùng được bao quanh đó.

Sau khi chạy đầu ra sẽ là

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Nếu bảng không có, sau đó trả lại bảng trống

• cho tôi trong phạm vi từ 0 đến số hàng - 1 -

  • if board [i, 0] =‘O’, then make_one (board, i, 0)

  • if board [i, length of row - 1] =‘O’, then make_one (board, i, length of row - 1)

• cho tôi trong phạm vi từ 0 đến số cols - 1 -

  • if board [0, i] =‘O’, then make_one (board, 0, i)

  • if board [count of row - 1, i] =‘O’, then make_one (board, count of row - 1, i)

• cho tôi trong phạm vi từ 0 đến số hàng

  • cho j trong phạm vi 0 đến số cols

    • nếu board [i, j] =‘O’ thì board [i, j] =‘X’, ngược lại là 1, board [i, j] =‘O’

• Make_one sẽ như thế nào -

• nếu tôi <0 hoặc j <0 hoặc i> =row count hoặc j> =col count hoặc board [i, j] =‘X’ hoặc board [i, j] =‘1’, thì trả về

• bảng [i, j]:=1

• gọi make_one (voard, i + 1, j), make_one (voard, i - 1, j), make_one (voard, i, j + 1), make_one (voard, i, j - 1)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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)

Đầu vào

[["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]

Đầu ra

[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]