Vùng bị bao quanh trong Python

Giả sử có bảng 2D chứa X và O. Bắt tất cả vùng bị bao quanh bởi X. Vùng bị bắt bằng cách đổi tất cả O thành X trong vùng đó.

Sau chạy, kết quả:

Để giải quyết, ta làm theo các bước −

• Nếu board không có, trả về board rỗng
• với i từ 0 đến số hàng - 1
  • nếu board[i][0] = 'O', gọi make_one(board, i, 0)
  • nếu board[i][len(row)-1] = 'O', gọi make_one(board, i, len(row)-1)
• với i từ 0 đến số cột - 1
  • nếu board[0][i] = 'O', gọi make_one(board, 0, i)
  • nếu board[số hàng-1][i] = 'O', gọi make_one(board, số hàng-1, i)
• với i từ 0 đến số hàng
  • với j từ 0 đến số cột
    • nếu board[i][j] = 'O', board[i][j] = 'X', ngược lại nếu là '1', board[i][j] = 'O'
• Hàm make_one:
• nếu i<0 hoặc j<0 hoặc i>=số hàng hoặc j>=số cột hoặc board[i][j]='X' hoặc board[i][j]='1', trả về
• board[i][j] := '1'
• gọi make_one(board, i+1, j), make_one(board, i-1, j), make_one(board, i, j+1), make_one(board, i, j-1)

Xem triển khai sau −

Ví dụ

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

Đầu vào

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

Kết quả

[['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X'], ['X', 'O', 'X', 'X']]