### Surrounded Regions

Idea: This problem cannot use simple DFS, because there is case as below, which will cause stack-overflow.

OOOOOOOOOO
XXXXXXXXXO
OOOOOOOOOO
OXXXXXXXXX
OOOOOOOOOO
XXXXXXXXXO
OOOOOOOOOO
OXXXXXXXXX
OOOOOOOOOO
XXXXXXXXXO


Good solution should be:

1. BFS
2. Union Find (with compressed path, otherwise TLE)
// BFS
void bfs(vector<vector<char>>& bd, int i, int j, int m, int n)
{
queue<pair<int,int>> Q;
Q.push({i, j});
bd[i][j] = '#';
while (!Q.empty())
{
pair<int, int> p = Q.front();
Q.pop();
i = p.first, j = p.second;
if (i > 0 && bd[i - 1][j] == 'O')
{
Q.push({i - 1, j});
bd[i - 1][j] = '#';
}
if (i < m - 1 && bd[i + 1][j] == 'O')
{
Q.push({i + 1, j});
bd[i + 1][j] = '#';
}
if (j > 0 && bd[i][j - 1] == 'O')
{
Q.push({i, j - 1});
bd[i][j - 1] = '#';
}
if (j < n - 1 && bd[i][j + 1] == 'O')
{
Q.push({i, j + 1});
bd[i][j + 1] = '#';
}
}
}
void solve(vector<vector<char>>& board)
{
int m = board.size();
int n = m ? board.size() : m;
if (m * n == 0)
return;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (board[i][j] == 'O' && (i == 0 || j == 0 || i == m - 1 || j == n - 1))
bfs(board, i, j, m, n);
}
}
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
board[i][j] = board[i][j] == 'O' ? 'X' :
board[i][j] == '#' ? 'O' : board[i][j];
}
}
}


Or Union Find:

int find(vector<int>& father, int id)
{
int orig = id;
int fa = father[id];
while (fa != id)
{
id = fa;
fa = father[id];
}
id = orig;
while (id != fa)
{
int fa_temp = father[id];
father[id] = fa;
id = fa_temp;
}
return fa;
}
void solve(vector<vector<char>>& board)
{
int m = board.size();
int n = m ? board.size() : m;
if (m * n == 0)
return;
vector<int> father(m * n + 1, -1);
for (int i = 0; i <= m * n; i++)
father[i] = i;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (board[i][j] == 'O' && (i == 0 || i == m - 1 || j == 0 || j == n - 1))
{
father[i * n + j] = m * n;
}
}
}
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (board[i][j] == 'X')
continue;
int offset = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
for (int k = 0; k < 4; k++)
{
int ii = i + offset[k];
int jj = j + offset[k];
if (ii < 0 || jj < 0 || ii >= m || jj >= n || board[ii][jj] == 'X')
continue;
int fa0 = find(father, i * n + j);
int fa = find(father, ii * n + jj);
if (fa != fa0)
father[min(fa, fa0)] = max(fa, fa0);
}
}
}
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (board[i][j] == 'O' && find(father, i * n + j) != m * n)
board[i][j] = 'X';
}
}
}