> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/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/algorithm-practice/leetcode/graph/694-number-of-distinct-islands.md).

# 694 Number of Distinct Islands

## 694. Number of Distinct Islands

## 1. Question

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.

## 2. Implementation

**(1) DFS**

```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}};
        String[] symbols = {"d", "u", "l", "r"};

        Set<String> set = new HashSet<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    StringBuilder key = new StringBuilder();
                    searchDistinctIslandByDFS(i, j, "s", key, directions, symbols, grid);

                    set.add(key.toString());
                }
            }
        }
        return set.size();
    }

    public void searchDistinctIslandByDFS(int row, int col, String symbol, StringBuilder key, int[][] directions, String[] symbols, int[][] grid) {
        grid[row][col] = 0;
        key.append(symbol);

        for (int i = 0; i < directions.length; i++) {
            int nextRow = row + directions[i][0];
            int nextCol = col + directions[i][1];

            if (isValid(nextRow, nextCol, grid)) {
                searchDistinctIslandByDFS(nextRow, nextCol, symbols[i], key, directions, symbols, grid);
            }
        }
        // back
        key.append("b");
    }

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

## 3. Time & Space Complexity

DFS: 时间复杂度O(mn), 空间复杂度O(mn)