Clear 9 lines C++ BFS with explanation


  • 0

    Explantion:
    We start with an island-grid, from that grid, we can go up, down, left, right - 4 directions, when we reach an island-grid connected to it, we set that grid to 0 to avoid re-visit that island grid. Each time we found a new island, num++, then return num.
    Extension:
    This problem is almost the same as LC.463 Island Perimeter, and here is my solution, almost same code.

        int numIslands(vector<vector<char>>& grid) {
            if(grid.size()==0) return 0;
            int num=0;
            for(int i=0;i<grid.size();i++)
                for(int j=0;j<grid[0].size();j++)
                    if(grid[i][j]=='1') BFS(grid,i,j),num++;
            return num;
        }
        
        int BFS(vector<vector<char>>& grid, int i,int j){
            if(i<0||j<0||i>grid.size()-1||j>grid[0].size()-1||grid[i][j]=='0') return 0;
            grid[i][j]='0';
            return BFS(grid,i-1,j)+BFS(grid,i,j-1)+BFS(grid,i+1,j)+BFS(grid,i,j+1);
        }
    

Log in to reply
 

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