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]