# 694. Number of Distinct Islands

Given a non-empty 2D array `grid` of 0's and 1's, an **island** is a group of `1`'s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Count the number of **distinct** islands. An island is considered to be the same as another if and only if one island can be translated (and not rotated or reflected) to equal the other.

**Example 1:**\


```
11000
11000
00011
00011
```

Given the above grid map, return `1`.

**Example 2:**\


```
11011
10000
00001
11011
```

Given the above grid map, return `3`.\
\
Notice that:

```
11
1
```

and

```
 1
11
```

are considered different island shapes, because we do not consider reflection / rotation.

**Note:** The length of each dimension in the given `grid` does not exceed 50.

```cpp
// DFS
void helper(vector<vector<int> >& grid, vector<vector<bool> >& visited, vector<vector<int> >& dirs, int x0, int y0, int i, int j, vector<pair<int, int> >& v) {
    if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] != 1 || visited[i][j]) return;
    visited[i][j] = true;
    v.push_back({i - x0, j - y0});
    for (auto dir : dirs) {
        int x = i + dir[0], y = j + dir[1];
        helper(grid, visited, dirs, x0, y0, x, y, v);
    }
}
int numDistinctIslands(vector<vector<int>>& grid) {
    if (grid.empty() || grid[0].empty()) return 0;
    set<vector<pair<int, int> > > res;
    int m = grid.size(), n = grid[0].size();
    vector<vector<bool> > visited(m, vector<bool>(n, false));
    vector<vector<int> > dirs({{1, 0}, {-1, 0}, {0, 1}, {0, -1}});
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] != 1 || visited[i][j]) continue;
            vector<pair<int, int> > v;
            helper(grid, visited, dirs, i, j, i, j, v);
            res.insert(v);
        }
    }
    return res.size();
}
```

```cpp
// DFS
void helper(vector<vector<int>>& grid, vector<vector<int> >& dirs, vector<vector<bool> >& visited, int x0, int y0, int i, int j, string& s) {
    if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] != 1 || visited[i][j]) return;
    visited[i][j] = true;
    s += to_string(i - x0) + "_" + to_string(j - y0);
    for (auto dir : dirs) {
        int x = i + dir[0], y = j + dir[1];
        helper(grid, dirs, visited, x0, y0, x, y, s);
    }
}
int numDistinctIslands(vector<vector<int>>& grid) {
    if (grid.empty() || grid[0].empty()) return 0;
    unordered_set<string> res;
    int m = grid.size(), n = grid[0].size();
    vector<vector<bool> > visited(m, vector<bool>(n, false));
    vector<vector<int> > dirs({{1, 0}, {-1, 0}, {0, 1}, {0, -1}});
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == 1 && !visited[i][j]) {
                string s;
                helper(grid, dirs, visited, i, j, i, j, s);
                if (!res.count(s)) res.insert(s);
            }
        }
    }
    return res.size();
}
```

```cpp
// DFS
void helper(const vector<vector<int> >& grid, vector<vector<bool> >& visited, int i, int j, string& s, string dir) {
    if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] != 1 || visited[i][j]) return;
    s.append(dir);
    visited[i][j] = true;
    helper(grid, visited, i - 1, j, s, "u");
    helper(grid, visited, i + 1, j, s, "d");
    helper(grid, visited, i, j - 1, s, "l");
    helper(grid, visited, i, j + 1, s, "r");
    s.append("b"); // back
}
int numDistinctIslands(vector<vector<int>>& grid) {
    if (grid.empty() || grid[0].empty()) return 0;
    int m = grid.size(), n = grid[0].size();
    unordered_set<string> res;
    vector<vector<bool> > visited(m, vector<bool>(n, false));
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == 1 && !visited[i][j]) {
                string s;
                helper(grid, visited, i, j, s, "o"); // origin
                if (!res.count(s)) res.insert(s);
            }
        }
    }
    return res.size();
}
```
