https://leetcode.com/problems/surrounded-regions/?tab=Description

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.

#### cpp

23ms, 32.42%, October 14, 2016

A really simple and readable C++ solution，only cost 12ms

• First, check the four border of the matrix. If there is a element is ‘O’, alter it and all its neighbor ‘O’ elements to ‘1’.
• Then ,alter all the ‘O’ to ‘X’
• At last,alter all the ‘1’ to ‘O’

https://discuss.leetcode.com/topic/1944/solve-it-using-union-find

Solve it using Union Find

Hi. So here is my accepted code using Union Find data structure. The idea comes from the observation that if a region is NOT captured, it is connected to the boundry. So if we connect all the ‘O’ nodes on the boundry to a dummy node, and then connect each ‘O’ node to its neighbour ‘O’ nodes, then we can tell directly whether a ‘O’ node is captured by checking whether it is connected to the dummy node.

For more about Union Find, the first assignment in the algo1 may help:

https://www.coursera.org/course/algs4partI

https://discuss.leetcode.com/topic/1944/solve-it-using-union-find/2

just another version in java:

https://discuss.leetcode.com/topic/18706/9-lines-python-148-ms

9 lines, Python 148 ms

Phase 1: “Save” every O-region touching the border, changing its cells to ‘S’.

Phase 2: Change every ‘S’ on the board to ‘O’ and everything else to ‘X’.

In case you don’t like my last line, you could do this instead:

https://discuss.leetcode.com/topic/2982/my-bfs-solution-c-28ms

My BFS solution (C++ 28ms)

The algorithm is quite simple: Use BFS starting from ‘O’s on the boundary and mark them as ‘B’, then iterate over the whole board and mark ‘O’ as ‘X’ and ‘B’ as ‘O’.

Note that one of the test cases is when the board is empty. So if you don’t check it in your code, you will encounter an run-time error.

https://discuss.leetcode.com/topic/25010/java-dfs-boundary-cell-turning-solution-simple-and-clean-code-commented

Java DFS + boundary cell turning solution, simple and clean code, commented.

https://discuss.leetcode.com/topic/6496/my-java-o-n-2-accepted-solution

My Java O(n^2) accepted solution

The idea is pretty simple: a ‘O’ marked cell cannot be captured whether:

1. It is in contact with the border of the board or
2. It is adjacent to an unflippable cell.

So the algorithm is straightforward:

1. Go around the border of the board
2. When a ‘O’ cell is found mark it with ‘U’ and perform a DFS on its adjacent cells looking for other ‘O’ marked cells.
3. When the entire border is processed scan again the board
• If a cell is marked as ‘O’ it wasn’t connected to unflippable cell. Hence capture it with ‘X’
• If a cell is marked as ‘X’ nothing must be done.
• If a cell is marked as ‘U’ mark it as ‘O’ because it was an original ‘O’ marked cell which satisfied one of the above conditions.
On a technical side regarding the code:

• In the problem statement it’s not specified that the board is rectangular. So different checks must performed when scanning the border.

• Since a pure recursive search causes stack overflow it’s necessary to make the DFS iterative using a stack to simulate recursion.