In the problem Surrounded Regions, DFS may yield stack overflow, why does it work in this problem? Anybody ever thought about it?
Why does DFS work in solving this problem?


If you keep track of what node has been visited, the maximum memory space will just be o(n).
void dfs(vector<vector<char>> &board, int a, int b){ stack<pair<int, int>>dp; dp.push(make_pair(a, b)); while (!dp.empty()){ pair<int, int> temp = dp.top(); dp.pop(); int x = temp.first; int y = temp.second; if (x < 0  y < 0  x >= board.size()  y >= board.front().size())continue; if (board[x][y] == 'O'){ board[x][y] = 'T'; } else{ continue; } dp.push(make_pair(x  1, y)); dp.push(make_pair(x + 1, y)); dp.push(make_pair(x, y  1)); dp.push(make_pair(x, y + 1)); } } void solve(vector<vector<char>> &board) { if (board.empty())return; for (int i = 0; i < board.front().size(); ++i){ dfs(board, 0, i); dfs(board, board.size()  1,i ); } for (int i = 0; i < board.size(); ++i){ dfs(board, i, 0); dfs(board, i, board.front().size()1); } for (int i = 0; i < board.size(); ++i){ for (int j = 0; j < board.front().size(); ++j){ if (board[i][j] == 'T'){ board[i][j] = 'O'; } else{ board[i][j] = 'X'; } } } }