DFS without stack overflow issues

• ``````public class Solution {
private class Point {
public int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public boolean isIllegal(char[][] board) {
return x >= 0 && x < board.length && y >= 0 && y < board[0].length;
}
}
public void solve(char[][] board) {
if (board != null && board.length > 0) {
for (int i = 0; i < board[0].length; i++) {
if (board[0][i] == 'O') {
update(board, 0, i);
}
if (board[board.length - 1][i] == 'O') {
update(board, board.length - 1, i);
}
}
for (int i = 0; i < board.length; i++) {
if (board[i][0] == 'O') {
update(board, i, 0);
}
if (board[i][board[0].length - 1] == 'O') {
update(board, i, board[0].length - 1);
}
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == '*') {
board[i][j] = 'O';
} else if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
}
}
private void update(char[][] board, int x, int y) {
Stack<Point> stack = new Stack<Point>();
stack.push(new Point(x, y));
while (!stack.isEmpty()) {
Point point = stack.pop();
if (point.isIllegal(board) && board[point.x][point.y] == 'O') {
board[point.x][point.y] = '*';
stack.push(new Point(point.x - 1, point.y));
stack.push(new Point(point.x + 1, point.y));
stack.push(new Point(point.x, point.y - 1));
stack.push(new Point(point.x, point.y + 1));
}
}
}
}
``````

• Can you explain how do you avoid that issue?

• it is a little different from you ,can you help me to explain my faults?

``````bool isValid(vector<vector<char>>& board,int m, int n, int i, int j) {
if (0 <= i&&i < m && 0 <= j&&j < n&& board[i][j] == 'O') {
return true;
}
return false;
}

void walk(vector<vector<char>>& board, int i, int j) {
queue<pair<int, int>>q;
q.push(make_pair(i, j));
int m = board.size(), n = board[0].size();

while (!q.empty()) {
pair<int, int>tem = q.front();
q.pop();
int k = tem.first, l = tem.second;
board[k][l] = '#';
if (isValid(board, m, n, k + 1, l))
q.push(make_pair(k + 1, l));
if (isValid(board, m, n, k - 1, l))
q.push(make_pair(k - 1, l));
if (isValid(board, m, n, k, l - 1))
q.push(make_pair(k, l - 1));
if (isValid(board, m, n, k, l + 1))
q.push(make_pair(k, l + 1));
}
}

void solve(vector<vector<char>>& board) {
if (board.empty() || board[0].empty())
return;
int m = board.size(), n = board[0].size();

for (int i = 0; i < m;i++) {
if (board[i][0] == 'O')
walk(board, i, 0);
if (board[i][n-1] == 'O')
walk(board, i, n-1);
}

for (int j = 0; j < n; j++) {
if (board[0][j] == 'O')
walk(board, 0, j);
if (board[m-1][j] == 'O')
walk(board, m-1, j);
}

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == '#')
board[i][j] = 'O';
else
board[i][j] = 'X';
}
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.