Easy to understand C++ recursive DFS with explanation using set of sets


  • 0

    Start by using my previous solution for max area of an island (https://discuss.leetcode.com/topic/106399/easy-to-understand-c-recursive-dfs). Modify this code to store each unique island by tracking the island coordinates relative to the top-left corner of the island ( i.e. the first coordinate of every island found will be [ 0, 0 ] ). This ensures that duplicate islands are NOT counted more than once. "Sink" the island cells as they are processed ( i.e. set the value to 0 ).

    class Solution {
    public:
        int numDistinctIslands(vector<vector<int>>& grid) {
            set<set<pair<int,int>>> islands;
            for (int r=0; r < grid.size(); ++r){
                for (int c=0; c < grid[0].size(); ++c){
                    if (grid[r][c]){
                        set<pair<int,int>> curr{};
                        dfs(grid,r,c,curr,make_pair(r,c));
                        islands.insert(curr);
                    }
                }
            }
            return (int)islands.size();
        }
        
        void dfs(vector<vector<int>>& grid, const int& r, const int& c,
                    set<pair<int,int>>& island, const pair<int,int>& start){
            if (!(0<=r&&r<grid.size() && 0<=c&&c<grid[0].size())) return;
            if (!grid[r][c]) return;
            island.insert(make_pair(r-start.first,c-start.second));
            grid[r][c]=0;
            dfs(grid,r-1,c,island,start); // top
            dfs(grid,r,c+1,island,start); // right
            dfs(grid,r+1,c,island,start); // bottom
            dfs(grid,r,c-1,island,start); // left
        }
    };
    

Log in to reply
 

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