Use stack to get rid of StackOverFlow in DFS

• Most people first use a recursion to traverse in board, but this will cause StackOverFlow in large size input. Use a stack to simulate the recursion will solve your problem.

``````class Pair {
int x;
int y;
Pair (int a, int b) { x = a; y = b; }
}

public void solve(char[][] board) {
int m = board.length;
if (m == 0) return;
int n = board[0].length;

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if ((i == 0 || j == 0 || i == m-1 || j == n-1)
&& board[i][j] == 'O') {
// for positions in border which are 'O', exhaust all NON surrounded regions and mark them as 'N'
Stack<Pair> stk = new Stack<Pair>();
stk.push(new Pair(i, j));
while (!stk.isEmpty()) {
Pair curr = stk.pop();
int x = curr.x;
int y = curr.y;
if (x < 0 || x >= m || y < 0 || y >= n || !(board[x][y] == 'O'))
continue;
board[x][y] = 'N';
stk.push(new Pair(x-1, y));
stk.push(new Pair(x, y-1));
stk.push(new Pair(x, y+1));
stk.push(new Pair(x+1, y));
}
}
}
}

// mark all NON surrounded regions back to 'O' and render all surrounded regions
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O') board[i][j] = 'X';
else if (board[i][j] == 'N') board[i][j] = 'O';
}
}
}``````

• This is a very good, clear dfs solution using stacks to simulate recursion. Thank you for sharing. However, I have a question about stack overflow. If the space used by stacks here is similar to the space used by the call stack of recursion, why the call stack gives us an overflow, while using stacks don't? Thanks.