# Number of Distinct Islands

`DFS`

**Medium**

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.

## Analysis & Solution

和Number of Islands的主要区别在于如何判断两个island是否是distinct；需要用HashSet/HashMap来存已找到的island，但是用什么作为Hash Key呢？

Shape一样，那么DFS搜索时的路径应该是一样的，那么反过来也成立。但是，有一个要注意的点是，DFS backtrack返回时，是因为碰到地图边缘了，还是因为旁边是海。这样就需要区别处理。

比如：

```
A = [[1,0],
     [1,1]]
B = [[1,1],
     [1,0]]
```

如果只记录up, down, left, right，那么两个island的signature也就是hash key都长得一样，但是加上何时上下左右四方都扫描完这个信息，就可以区分这两个island了。

@wavy: [https://leetcode.com/problems/number-of-distinct-islands/discuss/108475/Java-very-Elegant-and-concise-DFS-Solution(Beats-100\\](https://leetcode.com/problems/number-of-distinct-islands/discuss/108475/Java-very-Elegant-and-concise-DFS-Solution\(Beats-100\)/)

### DFS + HashSet (Hash by Path Signature)

```java
class Solution {
    public int numDistinctIslands(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        HashSet<String> islands = new HashSet<String>();
        int m = grid.length;
        int n = grid[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    StringBuilder sb = new StringBuilder();
                    dfs(grid, sb, "o", i, j);
                    islands.add(sb.toString());
                }
            }
        }

        return islands.size();
    }

    private void dfs (int[][] grid, StringBuilder sb, String dir, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) {
            return;
        }

        // mark the cell as visited
        grid[i][j] = 0;
        sb.append(dir);

        dfs(grid, sb, "u", i - 1, j);
        dfs(grid, sb, "l", i, j - 1);
        dfs(grid, sb, "d", i + 1, j);
        dfs(grid, sb, "r", i, j + 1);

        sb.append("x");
    }
}
```

### DFS + HashSet (Hash by Path Signature) Another One

```java
public int numDistinctIslands(int[][] grid) {
    Set<String> set = new HashSet<>();
    for(int i = 0; i < grid.length; i++) {
        for(int j = 0; j < grid[i].length; j++) {
            if(grid[i][j] != 0) {
                StringBuilder sb = new StringBuilder();
                dfs(grid, i, j, sb, "o"); // origin
                grid[i][j] = 0;
                set.add(sb.toString());
            }
        }
    }
    return set.size();
}
private void dfs(int[][] grid, int i, int j, StringBuilder sb, String dir) {
    if(i < 0 || i == grid.length || j < 0 || j == grid[i].length 
       || grid[i][j] == 0) return;
    sb.append(dir);
    grid[i][j] = 0;
    dfs(grid, i-1, j, sb, "u");
    dfs(grid, i+1, j, sb, "d");
    dfs(grid, i, j-1, sb, "l");
    dfs(grid, i, j+1, sb, "r");
    sb.append("b"); // back
}
```

### DFS + Hash By Local Coordinates <a href="#approach-1-hash-by-local-coordinates-accepted" id="approach-1-hash-by-local-coordinates-accepted"></a>

基本思想就是利用进入DFS时的相对起始点坐标`r0`, `c0`

```java
class Solution {
    int[][] grid;
    boolean[][] seen;
    Set<Integer> shape;

    public void explore(int r, int c, int r0, int c0) {
        if (0 <= r && r < grid.length && 0 <= c && c < grid[0].length &&
                grid[r][c] == 1 && !seen[r][c]) {
            seen[r][c] = true;
            shape.add((r - r0) * 2 * grid[0].length + (c - c0));
            explore(r+1, c, r0, c0);
            explore(r-1, c, r0, c0);
            explore(r, c+1, r0, c0);
            explore(r, c-1, r0, c0);
        }
    }
    public int numDistinctIslands(int[][] grid) {
        this.grid = grid;
        seen = new boolean[grid.length][grid[0].length];
        Set shapes = new HashSet<HashSet<Integer>>();

        for (int r = 0; r < grid.length; r++) {
            for (int c = 0; c < grid[0].length; c++) {
                shape = new HashSet<Integer>();
                explore(r, c, r, c);
                if (!shape.isEmpty()) {
                    shapes.add(shape);
                }
            }
        }

        return shapes.size();
    }
}
```

<https://leetcode.com/problems/number-of-distinct-islands/solution/>