05 Explore00_Stack and DFS_ Number of Islands_Chapter04

[zwkcoding]

Keywords: DFS， Recursion Notes：

• BFS vs DFS
  • traverse order BFS: tree's level-order traversal, the nodes closer to the root node will be traversed earlier. DFS: only trace-back and try another path after we reach the deepest node.
  • path BFS: find the shortest path DFS: not always the shortest path
  • Data Structre
    BFS: processing order conforms adding order, SO FIFO, AND SO queen DFS: processing order opposing adding order， SO LIFO， AND SO stack
• implement DFS USING recursion

  ///persudo code
  /*
  * Return true if there is a path from cur to target.
  */
  boolean DFS(Node cur, Node target, Set<Node> visited) {
  return true if cur is target;
  for (next : each neighbor of cur) {
      if (next is not in visited) {
          add next to visted;
          return true if DFS(next, target, visited) == true;
      }
  }
  return false;
  } 

  Above templete uses the implicit stack provided by the Call Stack

[zwkcoding]

Problem: Nums of Islands Solution ;

• one solution uses BFS refer to this issue #5
• another solution uses DFS, as with DFS, there are also two implements( use recursion or not)

• another solution uses Union-Find By the way, just counts the numbers , no need to know which grid belongs to which islands, see this compact solution: https://leetcode.com/explore/learn/card/queue-stack/232/practical-application-stack/1380/discuss/56589/C++-BFSDFS. If you need to know attribution relationship for every grid. you could use

  • Union-Find version solution https://github.com/liuyubobobo/Play-Leetcode-Explore/blob/master/Learn/Queue-and-Stack/04-Stack-and-DFS/01-Number-of-Islands/cpp-0200/main4.cpp
  • DFS version solution https://github.com/haoel/leetcode/blob/master/algorithms/cpp/numberOfIslands/NumberOfIslands.cpp

[zwkcoding]

HandCoding Code :)

# Solution use BFS
class Solution {
public:
    int numIslands(vector<vector<char> >& grid)  {
        int m = grid.size();
        int n = m ? grid[0].size() : 0;
        islands = 0;
        offset[] = {0, 1, 0, -1, 0};
        for(int i = 0; i < m; i++)  {
            for(int j = 0; j < n; j++)  {
                if(grid[i][j] == '1')  {
                    islands++;
                    grid[i][j] = '0';
                    queue<pair<int, int> > todo;
                    todo.push({i,j});
                    while(!todo.empty())  {
                        pair<int, int> p = todo.front();
                        todo.pop();
                        for (int k = 0; k < 4; k++)  {
                            int r = p.first + offset[k],;
                            int c = p.second + offset[k+1];
                            if(r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == '1')  {
                                grid[r][c] = '0';
                                todo.push({r,c});
                            }
                        }
                    }

                }
            }
        }
        return islands;
    }

};

# Solution uses DFS
class Solution  {
public:
    int numIslands(vector<vector<char> >& grid)  {
        int m = grid.size(), n = m ? grid[0].size() : 0, islands = 0;
        for(int i = 0; i < m; i++)  {
            for(int j = 0; j < n; j++)  {
                if (grid[i][j] == '1')  {
                    islands++;
                    eraseIslands(grid, i, j);
                }
            }
        }
        return islands;
    }

private:
    void eraseIslands(vector<vector<char> >& grid, int i, int j)  {
        int m = grid.size(), n = grid[0].size();
        if (i < 0 || i == m || j < 0 || j == n || grid[i][j] == '0')  {
            return;
        }
        grid[i][j] = '0';
        eraseIslands(grid, i - 1, j);
        eraseIslands(grid, i + 1, j);
        eraseIslands(grid, i, j - 1);
        eraseIslands(grid, i, j + 1);
    }
};