C++ DFS solution


  • 0
    G
    a DFS solution, just count times when we meet waters.
    class Solution {
    public:
        void dfs(vector<vector<int>>& grid, vector<vector<bool>>& flag, int x, int y, int& ans){
            if(x<0 || y<0 || x>= grid.size() || y>=grid[0].size() || grid[x][y] == 0) {ans++; return;}
            if(flag[x][y] == true) return;
            
            flag[x][y] = true;
             dfs(grid,flag,x-1,y,ans);
             dfs(grid,flag,x,y-1,ans);
             dfs(grid,flag,x+1,y,ans);
             dfs(grid,flag,x,y+1,ans);
        }
        int islandPerimeter(vector<vector<int>>& grid) {
            if(grid.empty()) return 0;
            vector<vector<bool>> flag(grid.size(),vector<bool>(grid[0].size(),false));
            int ans = 0;
            for(int i = 0; i<grid.size(); ++i)
                for(int j = 0; j<grid[0].size();++j)
                    if(grid[i][j] == 1){
                        dfs(grid,flag,i,j,ans);
                        return ans;
                    }
            return -1;
        }
    };
    

Log in to reply
 

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