Number of Distinct Islands

DFS

Medium

Given a non-empty 2D arraygridof 0's and 1's, an island is a group of1'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 givengriddoes 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\

DFS + HashSet (Hash by Path Signature)

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

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

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

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/