Vùng bị bao quanh (Surrounded Regions) trong Python

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

Sau khi chạy, kết quả sẽ là:

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

• Nếu board không tồn tại, trả về board rỗng.

• Với i từ 0 đến số hàng - 1:

  • Nếu board[i][0] == 'O', gọi bien_thanh_1(board, i, 0).
  • Nếu board[i][so_cot-1] == 'O', gọi bien_thanh_1(board, i, so_cot-1).

• Với i từ 0 đến số cột - 1:

  • Nếu board[0][i] == 'O', gọi bien_thanh_1(board, 0, i).
  • Nếu board[so_hang-1][i] == 'O', gọi bien_thanh_1(board, so_hang-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 bien_thanh_1:

  • Nếu i < 0 hoặc j < 0 hoặc i >= so_hang hoặc j >= so_cot hoặc board[i][j] == 'X' hoặc board[i][j] == '1', trả về.
  • board[i][j] := '1'.
  • Gọi đệ quy bien_thanh_1 cho 4 hướng: (i+1,j), (i-1,j), (i,j+1), (i,j-1).

Ví dụ

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.bien_thanh_1(board, i, 0)
            if board[i][len(board[0])-1] == 'O':
                self.bien_thanh_1(board, i, len(board[0])-1)
        for i in range(len(board[0])):
            if board[0][i] == 'O':
                self.bien_thanh_1(board, 0, i)
            if board[len(board)-1][i] == 'O':
                self.bien_thanh_1(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 bien_thanh_1(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.bien_thanh_1(board, i+1, j)
        self.bien_thanh_1(board, i-1, j)
        self.bien_thanh_1(board, i, j+1)
        self.bien_thanh_1(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"]]