3 solutions: iterative version of BFS and DFS, recursive version of DFS, C++ implementation


  • 0
    X

    BFS iterative solution using Queue:

    struct GridPoint {
        int x;
        int y;
        GridPoint(int _x=0, int _y=0) : x(_x), y(_y) {}
    };
    
    class Solution {
    public:
        int numIslands(vector<vector<char> > & grid) {
            if (grid.size() == 0) return 0;
            int m = grid.size();
            int n = grid[0].size();
            vector<vector<int> > visited(m, vector<int>(n, 0));
            return bfs(grid, visited, m, n);
        }
        
        int bfs(vector<vector<char> > & grid, vector<vector<int> > & visited, int m, int n) {
            int numLands = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (!visited[i][j] && grid[i][j] == '1') {
                        visited[i][j] = 1;
                        queue<GridPoint> q;
                        q.push(GridPoint(i, j));
                        while (!q.empty()) {
                            GridPoint tmp = q.front(); q.pop();
                            //if right is feasible
                            if (tmp.y + 1 < n && !visited[tmp.x][tmp.y+1]) {
                                visited[tmp.x][tmp.y + 1] = 1;
                                if (grid[tmp.x][tmp.y + 1] == '1')
                                    q.push(GridPoint(tmp.x, tmp.y + 1));
                            }
                            //if down is feasible
                            if (tmp.x + 1 < m && !visited[tmp.x + 1][tmp.y]) {
                                visited[tmp.x + 1][tmp.y] = 1;
                                if (grid[tmp.x + 1][tmp.y] == '1')
                                    q.push(GridPoint(tmp.x + 1, tmp.y));
                            }
                            //pay attention: left should also be considered!
                            if (tmp.y - 1 >= 0 && !visited[tmp.x][tmp.y - 1]) {
                                visited[tmp.x][tmp.y - 1] = 1;
                                if (grid[tmp.x][tmp.y - 1] == '1')
                                    q.push(GridPoint(tmp.x, tmp.y-1));
                            }
                            //pay attention: up should also be considered!
                            if (tmp.x - 1 >= 0 && !visited[tmp.x - 1][tmp.y]) {
                                visited[tmp.x - 1][tmp.y] = 1;
                                if(grid[tmp.x - 1][tmp.y] == '1')
                                    q.push(GridPoint(tmp.x - 1, tmp.y));
                            }
                        }
                        numLands++;
                    }
                }
            }
            
            return numLands;
        }
    };
    

    DFS iterative solution using stack:

    struct GridNode {
        int x;
        int y;
        GridNode(int _x=0, int _y=0) : x(_x), y(_y) {}
    };
    
    //dfs iterative solution
    class Solution {
    public:
        int numIslands(vector<vector<char> > & grid) {
            if (grid.size() == 0) return 0;
            int m = grid.size();
            int n = grid[0].size();
            vector<vector<int> > visited(m, vector<int>(n, 0));
            return dfs(grid, visited, m, n);
        }
        
        int dfs(vector<vector<char> > & grid, vector<vector<int> > & visited, int m, int n) {
            int numLands = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (!visited[i][j] && grid[i][j] == '1') {
                        visited[i][j] = 1;
                        stack<GridNode> s;
                        s.push(GridNode(i, j));
                        
                        while (!s.empty()) {
                            GridNode curNode = s.top();
                            GridNode nextNode;
                            bool canContinue = true;
                            //check if current node can continue to go to next
                            //if can, choose one adjacent node to push to stack
                            if (curNode.x + 1 < m && !visited[curNode.x + 1][curNode.y] && grid[curNode.x + 1][curNode.y] == '1') {
                                nextNode = GridNode(curNode.x + 1, curNode.y);
                            } else if (curNode.y + 1 < n && !visited[curNode.x][curNode.y + 1] && grid[curNode.x][curNode.y + 1] == '1') {
                                nextNode = GridNode(curNode.x, curNode.y + 1);
                            } else if (curNode.x - 1 >= 0 && !visited[curNode.x - 1][curNode.y] && grid[curNode.x - 1][curNode.y] == '1') {
                                nextNode = GridNode(curNode.x - 1, curNode.y);
                            } else if (curNode.y - 1 >= 0 && !visited[curNode.x][curNode.y - 1] && grid[curNode.x][curNode.y - 1] == '1') {
                                nextNode = GridNode(curNode.x, curNode.y - 1);
                            } else {
                                canContinue = false;
                            }
                            
                            if(canContinue) {
                                visited[nextNode.x][nextNode.y] = 1;
                                s.push(nextNode);
                                curNode = nextNode;
                                continue;
                            }
                            
                            //if not, pop the top element of the stack
                            s.pop();
                            
                        }
                        
                        numLands++;
                    }
                }
            }
            
            return numLands;
        }
    };
    

    DFS recursive version:

    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 numLands = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == '1') {
                        dfs(grid, i, j, m, n);
                        numLands++;
                    }
                }
            }
            return numLands;
        }
        
        void dfs(vector<vector<char> >& grid, int x, int y, int m, int n) {
            grid[x][y] = '2'; //2 indicates that this position is visited
            //visit all node in adjacent list
            if (x + 1 < m && grid[x + 1][y] == '1') {
                dfs(grid, x + 1, y, m, n);
            }
            
            if (y + 1 < n && grid[x][y + 1] == '1') {
                dfs(grid, x, y + 1, m, n);
            }
            
            if (x - 1 >= 0 && grid[x - 1][y] == '1') {
                dfs(grid, x-1, y, m, n);
            } 
            
            if (y - 1 >= 0 && grid[x][y - 1] == '1') {
                dfs(grid, x, y-1, m, n);
            }
        }
    };
    

    Actually BFS cannot be implemented using recursion, if anyone knows how, please tell me? Thanks!


Log in to reply
 

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