130. Surrounding areas

Title Source: LeetCode https://leetcode-cn.com/problems/surrounded-regions

subject

Given a two-dimensional matrix containing 'X' and 'o' (letter O).

Find all areas surrounded by 'X' and fill all 'O' in these areas with 'X'.

Example:

X X X X
X O O X
X X O X
X O X X

After running your function, the matrix becomes:

X X X X
X X X X
X X X X
X O X X

Explanation:

The enclosed interval will not exist on the boundary. In other words, the 'O' on any boundary will not be filled with 'X'. Any 'O' that is not on the boundary or connected to the 'O' on the boundary will eventually be filled with 'X'. If two elements are adjacent horizontally or vertically, they are said to be "connected".

Problem solving ideas

Idea: DFS, BFS

First look at the topic. A given two-dimensional matrix contains' X 'and' o '(letter O). Let's look at the explanation. The 'o' on any boundary will not be filled with 'X'. Now, that is to say, there are actually three parts:

• Can form enclosed 'X';
• 'O' surrounded by 'X';
• 'O' not surrounded by 'X'.

Now the requirement of the topic is to change the surrounded 'O' into 'X'. As mentioned earlier, the 'O' not surrounded is on the boundary. At the same time, the side shows that the 'O' connected to the boundary 'O' will not be filled by 'X'.

Then, according to this property, we can consider spreading from the boundary. First mark the 'O' that cannot be filled, that is, the part connected with the boundary 'O', and the remaining 'O' will be surrounded and transformed into 'X'. The specific methods are as follows:

• Take the 'O' of the boundary as the starting point and mark the letter 'O' connected or indirectly connected with it;

• When the 'O' of the upper part is marked, it starts to traverse the matrix to judge each letter (Note: the marked part will not be replaced):

  • If the letter is the marked part, convert it back to 'O';
  • If the letter is an unmarked department, convert it to 'X'.

Note: the title requires in-situ modification, so when we mark, the part connected with boundary 'O' (including boundary 'O') is marked as'M '.

We now use depth first search (DFS) and breadth first search (BFS) to solve this problem. The specific code is as follows.

code implementation

#Depth first search (DFS)
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board or len(board)==0:
            return

        def dfs(board, i, j):
            # If it is not in the matrix, or if it has been marked, skip directly
            if not (0<=i<m) or not (0<=j<n) or board[i][j] != 'O':
                return
            
            # When an 'O' that is identified as unlabeled and directly or indirectly connected to the boundary 'O', it is marked as'M '
            board[i][j] = 'M'
            # Spread to four directions
            # Up, down, left and right
            dfs(board, i-1, j)
            dfs(board, i+1, j)
            dfs(board, i, j-1)
            dfs(board, i, j+1)
            

        m = len(board)
        n = len(board[0])

        # Search from 'O' of boundary
        for i in range(m):
            for j in range(n):
                # First confirm whether i and j are at the boundary
                is_frontier = (i == 0 or j == 0 or i == m-1 or j == n-1)
                if is_frontier and board[i][j] == 'O':
                    dfs(board, i, j)
        
        # Traverse the two-dimensional array and convert the marked'M 'to' O ', and the unmarked one to' X '
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                if board[i][j] == 'M':
                    board[i][j] = 'O'

# Breadth first search (BFS)
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board or len(board) == 0:
            return
        
        m = len(board)
        n = len(board[0])

        from collections import deque
        queue = deque()

        # bfs is different from dfs and continues to search in the direction that meets the conditions
        # All bfs that meet the conditions must be queued
        # Join the 'O' of the border first
        for i in range(m):
            # Here are the leftmost and rightmost columns of a two-dimensional matrix
            if board[i][0] == 'O':
                queue.append((i, 0))
            if board[i][n-1] == 'O':
                queue.append((i, n-1))
        
        for j in range(n):
            # Here are the first and last rows of the two-dimensional matrix
            if board[0][j] == 'O':
                queue.append((0, j))
            if board[m-1][j] == 'O':
                queue.append((m-1, j))
        
        # Now start to get out of the team. At present, all the 'O's inside the border
        # When leaving the queue, mark and find the part connected with the boundary 'O' to join the queue
        while queue:
            x, y = queue.popleft()
            board[x][y] = 'M'
            # Find connected parts
            for nx, ny in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
                if 0 <= nx < m and 0 <= ny < n and board[nx][ny] == 'O':
                    queue.append((nx, ny))
        
        # Similarly, after marking, traverse the whole two-dimensional matrix for conversion
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                if board[i][j] == 'M':
                    board[i][j] = 'O'

Implementation results

Welcome to pay attention

Official account[ Collection of books]