DFS without stack overflow issues


  • 0
    J
    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));
                }
            }
        }
    }
    

  • 0
    O

    Can you explain how do you avoid that issue?


  • 0
    J

    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';
    		}
    	}
    }
    

Log in to reply
 

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