130. 被围绕的区域

题目链接

解题思路：通常想法是，把哪些'O'变成'X'，这种想法很难做。一个比较简单点是，「哪些'O'不能变成'X'」。其实就是与第一行，最后一行，第一列，最后一列，「相邻的这些」'O'，不能变成'X'，其他的都能变成' X'.

• 具体来说，把第一行、最后一行、第一列、最后一列的'O'，通过「感染」函数，变成'1'
• 然后遍历一遍，'1'就是不能变成'X'，其他的全部都变成'X'

代码

class Solution:
    def process(self, board: List[List[str]], i: int, j: int) -> None:
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != 'O':
            return
        board[i][j] = '1'
        self.process(board, i - 1, j)
        self.process(board, i + 1, j)
        self.process(board, i, j - 1)
        self.process(board, i, j + 1)

    def solve(self, board: List[List[str]]) -> None:
        if not board:
            return
        m, n = len(board), len(board[0])
        for i in range(m):
            self.process(board, i, 0)
            self.process(board, i, n - 1)
        for j in range(n):
            self.process(board, 0, j)
            self.process(board, m - 1, j)
        for i in range(m):
            for j in range(n):
                if board[i][j] == '1':
                    board[i][j] = 'O'
                else:
                    board[i][j] = 'X'