requirements

Given an m x n matrix board, consisting of characters’ x ‘and ‘O’, find all the regions surrounded by’ x ‘and fill all the ‘O’ in those regions with’ x ‘.

Example 1:

Input: board = [[" X ", "X", "X", "X"], [" X ", "O", "O", "X"], [" X ", "X", "O", "X"], [" X ", "O", "X", "X"]] output: [[" X ", "X", "X", "X"], [" X ", "X", "X", "X"], [" X ", "X", "X", "X"], [" X ", "O", "X", "X"]] : The bounded interval does not exist on the boundary, in other words, 'O' on any boundary will not be filled with 'X'. Any 'O' that is not on the boundary, or is not connected to the 'O' on the boundary, will eventually be filled with 'X'. Two elements are said to be "contiguous" if they are adjacent horizontally or vertically.Copy the code

Example 2:

Input: board = [["X"]] Output: [["X"]Copy the code

Tip:

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 200
  • [I][j] = ‘X’ or ‘O’

The core code

class Solution:
    def solve(self, board: List[List[str]]) - >None:
        """ Do not return anything, modify board in-place instead. """
        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":
                        self.saved(board,i,j)
        for i in range(len(board)):
            for j in range(len(board[i])):
                if board[i][j] == "O":
                    board[i][j] = "X"
        for i in range(len(board)):
            for j in range(len(board[i])):
                if board[i][j] == "A":
                    board[i][j] = "O"
    
    def saved(self,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":
                    self.saved(matrix,x,y)
Copy the code

Step 1: Find the edge O and change it and its adjacent O to A. Step 2: Any O that does not become A should become X; Step 3: Change the A back to the original O. The first notable part: we can see that the first part I in [0,len(board) -1] is the edge part; The second thing worth noting is that the saved function [[0,1],[0,-1],[1,0],[-1,0]] is exactly the point above, below, around the selected point.