[Leetcode] Surrounded Regions

Problem

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

If an "O"  is on the boundary of board, we call it boundary "O". 

For an "O", if there is a path containing only "O" to a boundary "O", we call it "live" "O". 

If an "O" is not "live", it must be surrounded by "X", and we need to flip it. 

Consider the 2D matrix as a graph, where "O"s are nodes. Adjacent "O"s are connected. We can perform a BFS starting from each "O" on the boundary, to find all "live" "O"s. Once we found all "live" "O"s, the rest need to be flipped. 

Note, recursive DFS may result in stack overflow for large matrix.

Code