Question

Formatted question description: https://leetcode.ca/all/130.html

130	Surrounded Regions

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,
X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

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



Algorithm

It’s a bit like “Go” chess, turning all the enclosed O into X, but the difference is that the O on the edge is not counted as being captured.

It is similar to the previous number of Islands and can be solved by DFS. At the beginning, my idea was that DFS traverses the O in the middle. If it does not reach the edge, it becomes X. If it reaches the edge, it changes back to the X before it.

However, it is very expensive to do this. The common practice seen on the Internet is to scan the four sides of the matrix. If there is an O, use DFS to traverse and change all consecutive Os into another character, such as $, so that the remaining The next Os are all captured, then change these Os into X, and change the$ back to O.

Java