Why does DFS work in solving this problem?


  • 0
    C

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


  • 0
    E

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

  • 0
    C

    Do you mean using hash table or else to record each node visited? I fail to get your point.


  • 0
    C
    This post is deleted!

  • 0
    C
    This post is deleted!

  • 0
    E
    This post is deleted!

Log in to reply
 

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