# 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'
# 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'

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'

## Welcome to pay attention

Official account[ Collection of books]

Tags: leetcode

Posted by sps on Tue, 24 May 2022 10:58:14 +0300