{leetcode}/problems/surrounded-regions/[LeetCode - Surrounded Regions^]
这道题的关键点在于找到入口。对我们来说,入口就是边界的的 O
,然后与之相连的 O
,其他的 O
都会被替换为 X
。为了区别对待,可以把识别出来的 O
替换为其他的字符,比如 #
。这样后期再遍历处理即可。
思考题:看题解可以使用 UnionFind 来解决这个问题。可以思考一下,如何实现?
这道题与 0200-number-of-islands.adoc 类似。
Given a 2D board containing 'X'
and 'O'
(the letter O), capture all regions surrounded by 'X'
.
A region is captured by flipping all ’O'`s into ’X'`s in that surrounded region.
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
Explanation:
Surrounded regions shouldn’t be on the border, which means that any 'O'
on the border of the board are not flipped to 'X'
. Any 'O'
that is not on the border and it is not connected to an 'O'
on the border will be flipped to 'X'
. Two cells are connected if they are adjacent cells connected horizontally or vertically.
link:{sourcedir}/_0130_SurroundedRegions.java[role=include]