python实现leetcode之130. 被围绕的区域

解题思路

三步走
第一步：找到边缘的O，将它和与它临接的O都变为A
第二步：没有变为A的O都是应该变为X的
第三步：将A变回原来的O

130. 被围绕的区域

代码

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        # 找到边缘的O，将它和与它临接的O都变为A
        for i in range(len(board)):
            for j in range(len(board[i])):
                if i in [0, len(board)-1] or j in [0, len(board[i])-1]:
                    if board[i][j] == 'O':
                        saved(board, i, j)
        # 没有变为A的O都是应该变为X的
        for i in range(len(board)):
            for j in range(len(board[i])):
                if board[i][j] == 'O': board[i][j] = 'X'
        # 将A变回原来的O
        for i in range(len(board)):
            for j in range(len(board[i])):
                if board[i][j] == 'A': board[i][j] = 'O'


def saved(matrix, i, j):
    matrix[i][j] = 'A'
    for di in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
        x, y = i+di[0], j+di[1]
        if 0 <= x < len(matrix) and 0 <= y < len(matrix[i]):
            if matrix[x][y] == 'O':
                saved(matrix, x, y)