> For the complete documentation index, see [llms.txt](https://code.taozirui.com/lc/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code.taozirui.com/lc/graph-search/bfsdfs/number-of-distinct-islands.md).

# 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.

Thoughts:

1. Distinct islands: island 2d coordinates sets are distinct **based off its offset**

**Code: Java**

```java
class Solution {
    private static final int d [] = {0,1,0,-1,0};

    public int numDistinctIslands(int[][] grid){
        int m = grid.length, n = grid[0].length;
        Set<List<List<Integer>>> distinctIslands = new HashSet<>();
        for(int i = 0; i < m; i ++){
            for(int j = 0; j < n; j++){
                List<List<Integer>> island = new ArrayList<>();
                if (dfs(i, j, i, j, grid, m, n, island)){
                    distinctIslands.add(island);
                }
            }
        }

        return distinctIslands.size();
    }

    private boolean dfs(int i, int j, int x, int y, int[][] grid, int m, int n, List<List<Integer>> island ){
        if(x < 0 || x >= m || y < 0 || y >= n || grid[x][y] <= 0) return false; // 1: island, -: visited path
        grid[x][y] = -1;
        island.add(Arrays.asList(x - i, y - j));
        for( int k = 0; k < 4; k ++){
            dfs(i, j, x + d[k], y + d[k + 1], grid, m, n, island);
        }

        return true;
    }
}
```

**Code: C++**

```cpp
class Solution {
public:
    int numDistinctIslands(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        set<vector<vector<int>>> distinctIslands;
        for(int i = 0; i < m; i ++){
            for(int j = 0; j < n; j++){
                vector<vector<int>> island;
                if (dfs(i, j, i, j, grid, m, n, island)){
                    distinctIslands.insert(island);
                }
            }
        }
        return distinctIslands.size();
    }
private:
    int d [5]  = {0,1,0,-1,0};

    bool dfs(int i, int j, int x, int y, vector<vector<int>> & grid, int m, int n, vector<vector<int>> & island){
        if(x < 0 or x >= m or y < 0 or y >= n or grid[x][y] <= 0) return false;
        grid[x][y] *= -1;
        island.emplace_back(x-i, y-j);
        for(int k = 0; k < 4; k++){
            dfs(i, j, x + d[k], y + d[k + 1], grid, m, n, island);
        }

        return true;
    }

};
```