C++ use queue(BFS) TLE but stack(DFS) AC


  • 0
    J
    class Solution {
    public:
        int numIslands(vector<vector<char>>& grid) {
            if(grid.size() == 0){
                return 0;
            }
            int m = grid.size();
            int n = grid[0].size();
            int ret = 0;
            stack<pair<int, int>> s;
            vector<vector<bool>> visited(m, vector<bool>(n, false));
            for(int i = 0; i < m; i++){
                for(int j = 0; j < n; j++){
                    if(grid[i][j] == '1' && !visited[i][j]){
                        ret++;
                        s.push(make_pair(i, j));
                        while(!s.empty()){
                            pair<int, int> cur = s.top();
                            s.pop();
                            int x = cur.first;
                            int y = cur.second;
                            visited[x][y] = true;
                            if((x+1) < m && grid[x+1][y] == '1' && !visited[x+1][y]){
                                s.push(make_pair(x+1, y));
                            }
                            if((x-1) >=0 && grid[x-1][y] == '1' && !visited[x-1][y]){
                                s.push(make_pair(x-1, y));
                            }
                            if((y+1) < n && grid[x][y+1] == '1' && !visited[x][y+1]){
                                s.push(make_pair(x, y+1));
                            }
                            if((y-1) >= 0 && grid[x][y-1] == '1' && !visited[x][y-1]){
                                s.push(make_pair(x, y-1));
                            }
                        }
                    }
                }
            }
            return ret;
        }
    };
    

    This above one passed, but below got a TLE

    class Solution {
    public:
        int numIslands(vector<vector<char>>& grid) {
            if(grid.size() == 0){
                return 0;
            }
            int m = grid.size();
            int n = grid[0].size();
            int ret = 0;
            queue<pair<int, int>> q;
            vector<vector<bool>> visited(m, vector<bool>(n, false));
            for(int i = 0; i < m; i++){
                for(int j = 0; j < n; j++){
                    if(grid[i][j] == '1' && !visited[i][j]){
                        ret++;
                        q.push(make_pair(i, j));
                        while(!q.empty()){
                            pair<int, int> cur = q.front();
                            q.pop();
                            int x = cur.first;
                            int y = cur.second;
                            visited[x][y] = true;
                            if((x+1) < m && grid[x+1][y] == '1' && !visited[x+1][y]){
                                q.push(make_pair(x+1, y));
                            }
                            if((x-1) >=0 && grid[x-1][y] == '1' && !visited[x-1][y]){
                                q.push(make_pair(x-1, y));
                            }
                            if((y+1) < n && grid[x][y+1] == '1' && !visited[x][y+1]){
                                q.push(make_pair(x, y+1));
                            }
                            if((y-1) >= 0 && grid[x][y-1] == '1' && !visited[x][y-1]){
                                q.push(make_pair(x, y-1));
                            }
                        }
                    }
                }
            }
            return ret;
        }
    };
    

    The only difference of these two code is the stack and queue.

    Assume that iterative is faster than recursive so I did not consider recursive(DFS) for now. How can I choose between BFS and DFS, in this case these two approaches should be the same.

    Thanks in advance for any help.


  • 0
    U

    Mark, wait for the captain


  • 0
    W

    Say, there are three points in queue, [a, b, c]
    When you handle a, you may have already visited b and c, but b and c have already in the queue.
    Thus, your code will compute b and c repeatedly.


Log in to reply
 

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