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

• 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
}
};
``````

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