DFS and BFS in C++


  • 29

    When we met a '1', the answer add 1, we also need to search all '1' which connected to it directly or indirectly, and change it to '0'. And we can use DFS or BFS to search.

    1. DFS
      ======
      class Solution
      {
      public:
      int numIslands(vector<vector<char>> &grid)
      {
      if(grid.size() == 0 || grid[0].size() == 0)
      return 0;

           int res = 0;
           for(int i = 0; i < grid.size(); ++ i)
               for(int j = 0; j < grid[0].size(); ++ j)
                   if(grid[i][j] == '1')
                   {
                       ++ res;
                       DFS(grid, i, j);
                   }
           return res;
       }
      

      private:
      void DFS(vector<vector<char>> &grid, int x, int y)
      {
      grid[x][y] = '0';
      if(x > 0 && grid[x - 1][y] == '1')
      DFS(grid, x - 1, y);
      if(x < grid.size() - 1 && grid[x + 1][y] == '1')
      DFS(grid, x + 1, y);
      if(y > 0 && grid[x][y - 1] == '1')
      DFS(grid, x, y - 1);
      if(y < grid[0].size() - 1 && grid[x][y + 1] == '1')
      DFS(grid, x, y + 1);
      }
      };

    2. BFS
      ======

      class Solution
      {
      public:
      int numIslands(vector<vector<char>> &grid)
      {
      if(grid.size() == 0 || grid[0].size() == 0)
      return 0;

           int res = 0;
           for(int i = 0; i < grid.size(); ++ i)
               for(int j = 0; j < grid[0].size(); ++ j)
                   if(grid[i][j] == '1')
                   {
                       ++ res;
                       BFS(grid, i, j);
                   }
           return res;
       }
      

      private:
      void BFS(vector<vector<char>> &grid, int x, int y)
      {
      queue<vector<int>> q;
      q.push({x, y});
      grid[x][y] = '0';

           while(!q.empty())
           {
               x = q.front()[0], y = q.front()[1];
               q.pop();
               
               if(x > 0 && grid[x - 1][y] == '1')
               {
                   q.push({x - 1, y});
                   grid[x - 1][y] = '0';
               }
               if(x < grid.size() - 1 && grid[x + 1][y] == '1')
               {
                   q.push({x + 1, y});
                   grid[x + 1][y] = '0';
               }
               if(y > 0 && grid[x][y - 1] == '1')
               {
                   q.push({x, y - 1});
                   grid[x][y - 1] = '0';
               }
               if(y < grid[0].size() - 1 && grid[x][y + 1] == '1')
               {
                   q.push({x, y + 1});
                   grid[x][y + 1] = '0';
               }
           }
       }
      

      };


  • 4
    Y

    Can you help me to figure out why my solution using non-recursive BFS got TLE?

    Input:

    ["11111011111111101011",
     "01111111111110111110",
     "10111001101111111111",
     "11110111111111111111",
     "10011111111111111111",
     "10111111011101110111",
     "01111111111101101111",
     "11111111111101111011",
     "11111111110111111111",
     "11111111111111111111",
     "01111111011111111111",
     "11111111111111111111",
     "11111111111111111111",
     "11111011111110111111",
     "10111110111011110111",
     "11111111111101111110",
     "11111111111110111100",
     "11111111111111111111",
     "11111111111111111111",
     "11111111111111111111"]
    

    Code:

    class Solution 
    {
    public:
        const vector<vector<int>> dirVector={{0,1},{0,-1},{1,0},{-1,0}};
        const int dirCnt=dirVector.size();
        
        int numIslands(vector<vector<char>>& grid) 
        {
            if(grid.empty())
                return 0;
            const int m=grid.size();
            const int n=grid[0].size();
            int cnt=0;
            for(int i=0;i<m;++i)
            {
                for(int j=0;j<n;++j)
                {
                    if(grid[i][j]=='1')
                    {
                        ++cnt;
                        bfsDetector(i,j,m,n,grid);
                    }
                }
            }
            return cnt;
        }
    private:
        void bfsDetector(int i,int j,const int &m,const int &n,vector<vector<char>> &grid)
        {
            queue<vector<int>> q;
            q.push({i,j});
            /*Mark up all the adjacent '1'*/
            while(!q.empty())
            {
                auto p=q.front();
                q.pop();
                int x=p[0];
                int y=p[1];
                grid[x][y]='2';
                for(int k=0;k<dirCnt;++k)
                {
                    int newX=x+dirVector[k][0];
                    int newY=y+dirVector[k][1];
                    
                    if(newX<0 || newX>=m || newY<0 || newY>=n || grid[newX][newY]!='1')
                        continue;
                    else
                        q.push({newX,newY});
                }
            }
        }
    };

  • 0
    W

    I have such problem, too!!


  • 9
    L

    You should mark a point as 2 before you push it into the queue. Otherwise it would be pushed again when its neighbor is visited.


  • 0
    T

    yes, I have never think about it yet.


  • 0
    Y

    Thanks for the post. I found out that for BFS if use pair<int, int> rather than vector<int>, it would be much faster.


  • 1
    E

    Hi, I think in if(grid.size() == 0 || grid[0].size() == 0), the second condition is not possible, grid[0].size will be at least 1 when it pass the first condition.


  • 0

    @lightsam I think it should be "after", "mark a point as 2 after you push it into the queue".

    And I have a question, when it arrives the second recursion of BFS, does the data in the queue of the first recursion still exists? In a new recursion, the queue is new or the old one?

    Well, it seems there is only one queue during the whole precess. I am wondering how it happens, why it doesn't create a new queue in a new recursion?


  • 0

    @zhugejunwei Oh, I misunderstood it. It repeated search the whole grid, changing all connected "1"s to be "0", and finally only "0"s left in the grid.


  • 1
    B

    @makuiyu
    If using pair rather than vector here, it will become much more efficient.
    Also I think using pair here is more appropriate in some sense.


  • 0
    Y

    @yhcy1993 Mark a point as '2' before pushing it into the queue; otherwise the same point may be pushed into the queue multiple times.


  • 0
    L

    Does the BFS solution have O(mn) time complexity?


  • 0
    U

    @yhcy1993

    Did you find out the reason behind TLE. I'm getting the same thing for the following:

    void doVisitBFS(vector<vector<char> > &grid, int i, int j)
        {
            queue<pair<int, int> > visit_queue;
            visit_queue.push(make_pair(i, j));
            while(!visit_queue.empty())
            {
                auto front = visit_queue.front();
                visit_queue.pop();
                grid[front.first][front.second] = '0';
                vector<pair<int, int> > candidates{make_pair(front.first+1,  front.second), make_pair(front.first, front.second+1), \
                                                make_pair(front.first-1, front.second), make_pair(front.first, front.second-1)};
                for(auto choice : candidates)
                {
                    if(isValid(choice, grid) && grid[choice.first][choice.second] == '1')
                        visit_queue.push(choice);
                }
                
            }
        }
    

  • 0
    J

    @utkarsh24 said in DFS and BFS in C++:

    Did you find out the reason behind TLE. I'm getting the same thing for the following:

    The idea is that if you push all the pair into a queue before mark the grid, the same points might be pushed into queue multiple times. A better way to solve this is to mark before you push, so that the runtime is still O(mn)


Log in to reply
 

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