Create number-of-distinct-islands.cpp

kamyu104 · web-flow · commit 5039fcb8dbf8 · 2017-10-09T19:19:36.000+08:00
diff --git a/C++/number-of-distinct-islands.cpp b/C++/number-of-distinct-islands.cpp
@@ -0,0 +1,39 @@
+// Time:  O(m * n)
+// Space: O(m * n)
+
+class Solution {
+public:
+    int numDistinctIslands(vector<vector<int>>& grid) {
+        unordered_set<string> islands;
+        for (int i = 0; i < grid.size(); ++i) {
+            for (int j = 0; j < grid[0].size(); ++j) {
+                string island;
+                if (dfs(i, j, &grid, &island)) {
+                    islands.emplace(island);
+                }
+            }
+        }
+        return islands.size();
+    }
+
+private:
+
+    bool dfs(const int i, const int j,
+             vector<vector<int>> *grid, string *island) {
+        static const unordered_map<char, pair<int, int>>
+            directions = { {'l', {-1,  0} }, {'r', { 1,  0} },
+                           {'u', { 0,  1} }, {'d', { 0, -1} }};
+
+        if (i < 0 || i >= grid->size() ||
+            j < 0 || j >= (*grid)[0].size() ||
+            (*grid)[i][j] <= 0) {
+            return false;
+        }
+        (*grid)[i][j] *= -1;
+        for (const auto& kvp : directions) {
+            island->push_back(kvp.first);
+            dfs(i + kvp.second.first, j +kvp.second.second, grid, island);
+        }
+        return true;
+    }
+};
