Clear C++ BFS solution with explanation


  • 1

    We start with an island-grid, from that grid, we can go up, down, left, right - 4 directions, when we reach an island-grid(1-grid), continue, when we reach a water-grid(0-grid) or out-of-bound, then there must be a "Wall" and we simply return 1.
    To avoid re-visit an island grid, we set island-grid to -1 after we visited it.
    Related problem: LC.200 Number of Islands and my similar solution.

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

Log in to reply
 

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