> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/my-algorithm-summary/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/my-algorithm-summary/chapter1/breath-first-search/694-number-of-distinct-islands.md).

# 694 Number of Distinct Islands

## 694. [Number of Distinct Islands](https://leetcode.com/problems/number-of-distinct-islands/description/)

## 1. 题目：

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.

## 2. 思路

这题的难点在于如何表示island形状的唯一性，这里我们的方法是用一个List of List存储每个值为1的点与起始点的相对距离 {row, col}， 然后再把这个List of List放到Hashset里判断唯一性， 最后得到的Hashset的size就是我们要求的不同形状的岛屿的个数。时间复杂度和空间复杂度都为O(mn)

## 3. Implementation

```java
class Solution {
    public int numDistinctIslands(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int m = grid.length, n = grid[0].length;
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        Set<List<List<Integer>>> set = new HashSet<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    List<List<Integer>> hashKey = new ArrayList<>();
                    searchByBFS(i, j, directions, grid, hashKey);
                    set.add(hashKey);
                }
            }
        }
        return set.size();
    }

    public void searchByBFS(int row, int col, int[][] directions, int[][] grid, List<List<Integer>> hashKey) {
        grid[row][col] = 0;
        Queue<Integer> queue = new LinkedList<>();
        int n = grid[0].length;

        queue.add(row * n + col);

        while (!queue.isEmpty()) {
            int curPoint = queue.remove();
            int curRow = curPoint / n;
            int curCol = curPoint % n;

            for (int i = 0; i < 4; i++) {
                int nextRow = curRow + directions[i][0];
                int nextCol = curCol + directions[i][1];

                if (isValid(nextRow, nextCol, grid)) {
                    grid[nextRow][nextCol] = 0;
                    hashKey.add(Arrays.asList(nextRow - row, nextCol - col));
                    queue.add(nextRow * n + nextCol);
                }
            }
        }
    } 

    public boolean isValid(int row, int col, int[][] grid) {
        return row >= 0 && row < grid.length &&  col >= 0 && col < grid[0].length && grid[row][col] == 1;
    }
}
```