NumberOfDistinctIslands [source code]


public class NumberOfDistinctIslands {
static
/******************************************************************************/
class Solution {
    static int[][] increments = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int numDistinctIslands(int[][] grid) {
        Set<Integer> islands = new HashSet<> ();
        Set<int[]> set = new HashSet<> ();
        int[] tl;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                set.clear ();
                tl = new int[]{51, 51};
                dfs (i, j, grid, set, tl);
                if (set.size () > 0) {
                    int res = 0;
                    for (int[] xy : set) {
                        int x = xy[0] - tl[0], y = xy[1] - tl[1];
                        res += x * grid[0].length + y;
                    }
                    islands.add (res);
                }
            }
        }
        return islands.size ();
    }

    void dfs (int x, int y, int[][] grid, Set<int[]> set, int[] tl) {
        if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] <= 0)
            return;
        grid[x][y] = -1;
        if (x < tl[0])
            tl[0] = x;
        if (y < tl[1])
            tl[1] = y;
        set.add (new int[]{x, y});
        for (int[] increment : increments)
            dfs (x + increment[0], y + increment[1], grid, set, tl);
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        NumberOfDistinctIslands.Solution tester = new NumberOfDistinctIslands.Solution();
        int[][][] inputs = {
            {{1,1,0,0,0},{1,1,0,0,0},{0,0,0,1,1},{0,0,0,1,1}}, {{1}},
            {{1,1,0,1,1},{1,0,0,0,0},{0,0,0,0,1},{1,1,0,1,1}}, {{3}},
            {{1,1}}, {{1}},
            {{1},{1}}, {{1}},
            {{1,1,0,1,0,1,0,0,1,1,1,0,1,1,0,0,0,0,1,0,0,1,1,1,1,1,0,1,1,1,1,1,0,0,1,1,0,0,0,1,1,1,0,0,1,0,1,1,0,0},{1,0,0,0,1,1,0,0,1,0,1,0,1,1,0,0,1,0,1,1,0,1,1,0,0,0,0,1,1,1,0,0,1,1,0,1,1,1,0,1,1,0,0,1,0,0,1,0,0,1},{0,1,1,1,0,0,0,0,1,0,1,1,0,0,1,1,0,1,1,0,0,0,0,1,1,0,1,1,0,0,0,1,0,0,0,1,1,1,0,0,0,1,1,1,0,0,0,1,1,0},{1,1,1,1,1,0,0,0,1,1,0,0,1,0,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,1,0,0,1,1,0,1,0,0,1,0,0,0,0,1,0,1,1,1,1,1},{1,1,0,1,1,1,0,1,1,1,0,1,0,1,1,0,0,0,0,1,0,0,0,1,1,1,1,0,0,1,1,1,1,1,1,0,0,1,1,1,1,1,0,0,0,0,1,1,1,1},{0,1,1,1,1,0,1,0,1,1,0,0,0,1,1,0,1,0,1,0,1,1,1,1,0,0,1,1,0,0,0,0,0,1,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,0},{0,1,1,0,1,1,0,0,0,1,1,0,0,1,1,0,1,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,1,0,0,0,1,0,0,1,0,0,1,1,0,1,1,0},{0,1,0,0,1,0,1,1,1,1,0,0,0,1,0,1,1,0,1,1,0,1,1,1,0,1,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,1,0,1,0,1,0,0,1},{0,1,1,0,1,0,1,0,0,1,1,1,1,1,1,1,1,1,0,1,0,0,1,1,1,1,1,1,0,1,1,1,1,0,0,1,1,0,1,0,1,1,0,0,1,0,0,1,0,1},{0,1,0,0,1,1,1,0,0,1,0,0,0,0,0,0,1,1,1,0,1,0,0,0,0,1,1,1,1,0,1,1,0,1,1,1,1,0,0,0,1,1,0,1,0,1,1,1,1,1},{0,0,0,0,1,1,1,1,1,0,0,1,0,1,1,0,1,0,1,0,0,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,0},{1,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,1,0,1,1,1,0,1,1,1,1,0,0,1,1,1,0,0,1,0,0,1,1,0,1,1,1,0,0,1,1,0,1},{1,0,1,0,1,1,0,1,0,1,0,0,0,1,1,1,1,0,0,0,0,1,0,1,1,1,1,1,1,1,0,0,1,0,1,1,0,0,1,0,0,0,1,0,1,1,1,1,1,0},{1,0,0,0,0,0,0,0,1,0,1,1,0,0,0,1,1,1,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,0,0,1,1,0,0,0,0,1,1,0,0,0,1,0,1},{0,1,0,0,0,1,0,1,0,1,0,0,1,0,0,1,1,0,0,1,0,1,0,0,1,1,1,0,0,0,1,0,1,1,0,0,0,0,1,0,0,0,1,1,0,1,1,0,1,0},{0,0,1,0,0,1,0,1,1,0,1,0,0,0,1,0,1,0,1,1,1,0,1,0,0,1,0,0,1,0,1,1,1,0,0,0,1,1,0,1,0,1,0,1,0,1,0,0,1,0},{1,0,0,0,1,1,0,1,0,1,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,0,1,0,0,0,0,1,1,1,0,1,1,1,0,1,0,1,1,0,1,1,1,1,0},{1,0,0,0,0,0,1,1,1,1,0,0,0,1,1,0,1,0,1,1,1,1,1,0,1,0,1,1,0,0,0,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,0,1},{0,1,0,0,0,0,0,0,1,0,0,1,1,1,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,1,1,0,1,1,1,0,0,0,0},{0,1,1,0,1,1,0,0,0,0,0,1,0,1,0,0,1,1,1,1,0,0,0,1,1,1,1,0,1,1,0,1,1,1,0,1,1,0,1,0,0,1,0,0,0,1,0,1,1,1},{0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,0,1,1,1,0,1,1,0,1,1,1,0,1,1,0,0,1,0,1,0,1,1,0,1,1,1,1,1,0,1,0,1,0,1,0},{0,0,0,0,1,1,1,1,0,0,0,1,1,0,0,1,0,0,1,1,0,1,0,1,1,0,1,0,0,1,1,1,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,1},{1,0,0,0,1,1,0,0,0,1,0,1,1,0,1,1,0,1,0,1,1,0,0,0,1,1,0,0,1,0,0,0,0,1,1,0,0,1,1,1,0,0,0,1,1,0,0,1,1,0},{0,1,1,1,0,0,0,0,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,0,0,0,1,1,0,1,1,0,0,1,0,0,1,0,1,1,1,0,0,1,0,1},{1,1,1,0,1,0,0,1,1,1,0,1,1,1,0,1,1,0,0,1,1,0,1,0,0,0,0,0,1,1,1,0,0,1,0,1,0,0,0,1,1,1,1,1,0,1,0,1,0,1},{0,0,1,1,1,1,1,0,1,0,1,1,0,1,0,1,0,1,1,1,0,0,0,1,1,0,0,1,0,0,0,0,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0},{1,1,0,0,1,1,0,1,1,1,0,0,0,1,1,1,0,0,1,1,1,1,0,0,0,1,0,1,0,1,0,1,0,0,0,1,0,0,1,1,0,0,0,1,1,0,1,0,1,1},{1,1,0,1,1,1,0,1,1,0,0,1,1,1,1,0,0,0,0,0,0,1,1,1,0,0,1,1,0,0,1,0,1,1,1,0,1,0,0,1,0,1,0,1,1,1,1,0,0,0},{0,0,0,0,0,1,1,1,0,0,1,0,1,0,1,0,1,0,0,0,0,1,1,1,0,1,1,0,1,1,0,1,1,0,1,0,1,0,0,0,0,1,0,1,1,1,1,1,0,0},{0,1,1,1,1,1,0,1,0,1,1,0,0,1,0,0,1,1,1,1,1,1,0,0,1,0,0,0,0,1,1,0,0,1,1,0,1,1,0,0,1,0,1,0,0,1,0,0,1,0},{1,0,1,1,1,0,1,0,1,1,1,0,0,1,1,1,0,0,1,1,0,1,1,0,0,0,1,0,0,1,0,0,1,0,1,1,1,1,0,1,0,1,1,0,0,1,1,1,0,1},{0,0,1,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,0,0,1,1,0,1,1,1,0,0,1,1,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1,0,1,0,0,1},{0,1,1,0,1,0,0,0,1,0,1,0,0,1,1,0,1,1,0,0,1,1,0,0,0,1,1,1,0,1,1,0,1,1,1,0,1,1,1,1,1,0,0,0,1,0,0,0,1,1},{0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,0,0,1,0,1,0,1,0,1,0,0,1,0,1,0,0,1,1,1,0,1,0,0,1,1},{0,0,0,1,0,0,0,0,0,1,1,1,0,0,1,0,0,1,1,1,0,1,0,0,1,1,1,0,1,1,0,1,1,0,1,0,1,1,0,0,1,0,0,0,1,1,0,1,0,1},{1,1,1,1,1,0,1,0,0,1,0,0,0,1,1,1,0,0,1,0,1,0,1,0,1,1,0,1,0,1,0,0,1,1,1,1,0,1,1,0,1,1,0,1,1,1,0,1,0,1},{0,1,0,0,1,0,0,1,1,0,0,1,0,0,1,1,1,1,1,0,0,0,0,1,0,0,0,1,0,1,1,0,1,0,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,0},{0,0,0,1,1,0,0,1,0,1,0,0,0,0,1,0,0,0,1,0,1,1,0,1,1,1,0,1,1,0,1,0,1,0,0,1,1,0,0,0,0,1,1,0,1,1,0,0,1,1},{0,1,1,1,0,1,1,1,1,0,1,1,1,0,0,1,0,0,1,0,0,1,1,0,0,0,0,1,0,0,0,1,0,0,1,1,1,1,0,1,0,1,1,0,1,0,0,0,1,1},{1,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,1,1,0,1,1,0,0,1,1,1,0,1,0,0,1,1,1,1,1,1,1,1,1,0,1,1,1,0,0,1,1},{0,0,0,0,1,1,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,0,0,0,1,1,1,0,0,1,1,1,0,1,0,0,1,0,1,1,0,0,1,0,0,1,1,1,0,1},{1,1,1,1,0,1,1,0,0,1,0,0,1,1,0,1,1,0,0,0,0,0,1,0,0,0,0,1,0,0,1,1,1,1,0,1,0,0,0,0,0,0,1,0,0,1,0,0,1,1},{0,0,1,1,0,1,1,1,1,1,0,0,1,1,1,0,0,0,0,1,1,1,1,0,1,1,0,0,1,0,0,0,1,0,0,0,0,0,0,1,1,0,1,0,1,1,0,1,1,0},{0,1,0,0,1,0,0,0,1,0,1,1,1,1,1,1,0,1,0,1,1,0,0,1,1,0,1,1,1,1,1,1,0,1,0,1,1,0,0,0,0,1,1,0,0,1,0,1,1,1},{0,0,0,0,0,0,0,0,1,0,1,1,0,1,0,0,1,0,0,0,1,1,1,1,1,0,1,1,1,0,0,1,0,0,0,1,0,0,1,1,0,1,0,0,0,1,1,1,0,0},{0,1,1,0,0,1,0,0,1,1,0,1,1,0,0,1,0,1,1,0,1,0,0,0,1,0,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,1,0,1,1,1,1,1,0},{1,0,0,1,0,0,1,1,1,1,0,1,0,0,0,0,0,1,0,0,1,0,0,0,1,1,0,1,0,1,1,1,0,1,1,0,0,1,1,1,1,0,0,1,1,1,0,0,1,1},{0,1,0,1,0,0,1,1,1,0,1,0,0,0,0,1,1,1,0,1,0,1,1,1,1,1,0,1,0,0,1,1,0,0,1,1,1,1,0,1,1,1,1,1,0,1,0,1,0,1},{1,0,1,0,0,1,1,0,0,1,1,1,1,1,0,0,1,0,1,1,0,0,1,0,0,1,0,0,0,1,0,1,1,0,0,1,1,1,0,0,0,1,1,1,1,1,0,1,0,0},{0,1,0,0,0,1,1,0,0,0,1,1,1,0,1,1,0,0,0,0,1,0,0,0,1,1,0,0,1,1,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,0,0,1,0}}, {{67}},
            {{0,0,0,1,1,1,0,0,0,0,1,1,0,1,0,1,1,1,0,0,0,0,1,0,0,1,0,1,1,1,1,1,0,0,1,1,0,1,1,1,0,0,0,1,1,1,1,1,0,0},{1,0,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,0,0,1,0,1,0,1,0,1,1,1,1,1,1,0,0,1,0,1,1,1,1,0,0,1,0,0,0,0,0,1,0,1},{0,1,1,1,1,0,1,1,0,1,0,0,0,1,1,1,1,0,0,1,1,0,0,0,1,1,1,1,1,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,1,1,0,1},{1,1,1,0,1,1,1,0,1,1,0,0,1,1,0,0,1,1,1,1,0,1,0,0,1,1,0,0,1,0,1,0,1,1,0,1,0,1,0,1,0,0,0,0,1,0,0,0,0,0},{0,1,1,0,0,1,0,1,0,0,0,1,0,1,1,0,1,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,1,0,1,1,1,1,1,1,1,0,0,0,0},{1,0,1,1,1,1,1,1,0,1,0,0,1,1,1,1,0,0,1,0,1,0,0,1,0,0,1,0,0,0,0,1,0,1,0,1,1,0,1,1,1,0,1,1,1,1,0,0,1,0},{1,0,0,1,1,0,0,1,1,1,1,0,0,0,0,0,1,1,0,0,1,1,0,0,1,1,1,0,1,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1},{1,1,0,0,0,1,1,0,1,0,1,0,1,1,1,1,0,0,1,1,0,0,0,0,0,1,1,0,0,0,1,1,0,0,0,1,1,1,1,0,0,1,0,0,1,1,0,1,0,1},{1,0,0,0,0,0,0,0,1,1,0,0,1,0,0,1,0,0,1,0,0,0,1,0,0,0,0,1,0,0,1,0,1,0,1,1,1,1,0,0,0,0,0,0,1,0,1,1,1,1},{0,0,1,1,0,0,0,0,1,1,1,1,1,0,0,1,1,0,0,1,1,1,0,1,0,0,0,1,1,1,0,0,1,1,0,0,1,0,0,1,1,1,0,0,0,0,1,0,0,0},{0,0,0,1,1,1,0,0,0,1,0,0,0,1,0,1,0,1,1,0,0,1,1,1,1,0,0,0,0,0,1,1,1,0,1,1,1,0,0,1,1,1,1,0,0,0,0,0,1,1},{1,0,0,0,0,0,1,0,0,1,0,0,1,1,1,1,0,0,0,0,1,0,1,1,1,1,0,0,1,1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1},{0,0,0,0,0,1,0,0,1,0,0,1,0,1,1,0,1,1,1,1,1,1,0,1,0,0,0,1,1,0,0,1,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,1,1,0},{0,1,0,1,1,0,1,0,1,0,0,0,1,1,1,0,1,1,1,1,1,0,1,1,0,1,0,1,0,1,1,1,1,1,1,0,0,0,1,0,0,0,0,1,0,1,1,1,1,1},{1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,0,0,0,0,1,1,1,0,1,1,1,1,1,0,0,1,0,1,1,0,1,1,0,1,1,0,1,0,0,1,1,1,0,1,1},{1,1,0,1,1,1,1,0,1,1,0,1,0,0,0,1,1,0,0,0,1,1,1,1,0,0,0,1,1,0,1,0,1,1,0,1,1,0,1,0,0,0,0,0,0,0,1,1,0,1},{0,0,1,0,0,0,1,1,0,1,0,1,1,1,1,0,0,0,0,0,1,0,0,0,0,1,0,0,1,0,1,1,0,0,1,1,1,0,0,1,1,0,1,0,0,0,0,0,0,0},{0,1,0,0,0,0,0,0,1,0,1,1,0,0,0,1,1,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,1,1,1,0,1,0,0,1,1,0,1,0,0,0,0,1,0,0},{1,1,0,1,1,1,0,0,0,1,1,1,1,0,0,1,0,1,0,0,1,0,1,1,0,1,1,1,1,1,0,0,0,0,0,1,0,0,0,1,0,0,1,0,0,1,1,0,1,0},{1,1,1,0,0,0,1,0,1,0,1,1,1,0,1,1,0,0,1,1,1,1,1,0,0,0,0,0,1,1,1,0,1,0,1,0,0,1,0,0,1,1,1,0,1,0,0,0,0,1},{1,1,0,1,0,1,1,1,0,1,0,0,0,0,0,0,0,1,0,1,1,0,0,1,1,0,1,1,1,1,1,0,1,0,1,0,0,1,1,1,1,1,0,0,1,0,1,1,0,0},{1,0,1,0,1,0,0,0,0,1,0,0,1,0,0,1,0,1,1,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,0,0,0,1,1,1,1,0,1,1,0,1,0,0},{1,0,0,1,0,0,1,0,0,1,0,0,0,1,1,0,0,0,1,0,1,1,0,0,1,0,1,0,0,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,1,1,1,0},{0,1,1,1,1,1,1,0,0,0,1,1,0,0,1,1,0,0,0,0,1,0,0,0,0,1,0,0,0,1,1,0,0,1,0,1,0,1,1,1,0,0,0,1,0,0,0,0,1,1},{1,0,0,1,0,1,1,1,1,0,1,0,1,0,0,1,1,0,1,1,1,0,1,0,0,1,1,1,1,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,1},{0,1,1,1,1,0,1,1,0,0,1,0,0,0,1,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,1,1,1,1,0,0,1,1,1,1,1},{1,1,1,1,0,1,1,1,0,0,0,0,1,0,1,1,1,1,1,1,0,0,1,1,0,1,0,1,1,1,0,0,1,0,1,0,1,1,1,1,1,0,1,1,0,0,0,0,0,1},{0,1,0,0,0,1,1,0,1,1,0,0,1,0,1,1,0,1,0,0,0,1,1,1,1,0,1,0,1,1,0,0,1,0,0,1,1,1,1,1,0,1,1,1,1,1,0,0,1,0},{0,1,1,0,0,1,0,1,1,0,0,0,0,1,0,1,1,0,0,1,0,0,0,1,1,0,1,0,1,1,0,0,0,0,0,1,1,0,0,1,0,1,1,0,0,0,1,0,1,0},{0,0,1,0,1,0,0,0,1,0,1,1,0,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,0,1,0,0,0,1,0,0,0,0,0,0,0},{0,0,0,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,0,0,1,1,1,1,1,0,1,1,0,0,0,1,1,1,0,0,0,1,1,1,1,1,0,1,1,1,0,1,1,1},{0,1,1,0,0,1,1,1,0,1,1,1,0,1,0,0,0,1,1,0,1,1,1,0,0,0,0,0,0,0,0,1,0,0,0,1,1,0,0,1,1,1,1,0,0,0,1,0,0,0},{1,1,1,0,0,0,0,1,1,0,1,0,1,1,1,1,0,0,1,0,1,0,0,1,1,0,1,0,1,1,0,0,0,0,1,0,1,0,1,0,0,1,1,0,1,1,1,0,0,0},{0,0,1,0,1,0,0,0,1,1,0,1,1,1,1,1,1,0,1,1,0,0,1,0,1,0,0,0,0,0,0,1,0,1,0,0,0,0,1,1,1,0,0,0,0,0,1,0,0,0},{0,1,0,1,1,1,1,0,1,0,1,1,1,0,0,0,1,1,1,1,1,1,0,1,0,1,0,1,0,1,1,1,1,0,1,0,0,0,1,0,0,1,1,1,0,0,1,1,0,1},{0,0,1,1,0,0,0,0,1,0,0,1,1,0,0,0,0,0,0,0,1,0,0,1,1,0,0,1,1,0,1,0,1,0,0,0,1,1,1,1,1,1,0,0,1,1,0,0,1,0},{1,0,1,1,0,1,0,1,1,0,0,1,0,1,1,0,0,0,0,0,1,1,0,0,0,0,1,1,0,0,1,0,1,0,0,0,0,0,1,1,0,1,0,1,0,0,0,1,1,1},{0,1,0,0,1,1,1,1,1,1,1,1,0,0,1,0,0,0,0,1,0,0,1,0,0,1,1,0,0,0,0,1,0,1,1,1,1,0,1,1,1,0,0,0,0,0,0,0,1,0},{1,0,0,1,1,1,0,1,1,1,0,1,0,1,0,1,0,0,1,1,0,1,1,1,0,0,0,1,0,1,0,0,1,1,0,1,1,0,1,0,0,1,0,0,1,0,1,0,0,0},{0,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,1,1,0,1,1,1,0,1,0,0,0,1,1,0,1,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,0,0,0,0},{1,0,1,1,0,0,0,1,0,1,0,1,1,1,0,0,0,1,1,1,0,1,1,1,1,1,1,1,1,0,1,0,0,1,1,0,0,0,0,0,0,1,0,0,1,1,0,0,1,1},{0,1,0,0,0,1,1,1,1,0,1,0,1,0,1,1,0,1,0,1,0,1,0,1,0,0,1,1,0,1,1,1,1,0,0,1,0,0,1,1,0,0,0,1,1,1,1,0,1,1},{1,1,1,0,0,1,1,1,0,1,1,0,0,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1,0,1,0,1,0,0,0,1,1,1,1,0,1,0,0,1,0,0,1,1,1,0},{0,0,1,0,0,1,1,0,0,1,0,0,1,0,1,1,1,0,0,0,1,0,0,1,1,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,1,1,1,1,1,0,0,1},{0,0,0,1,0,0,1,0,0,0,0,1,1,1,0,1,0,0,0,1,0,0,1,1,0,0,0,1,0,1,0,0,0,0,1,1,1,0,0,1,1,0,1,0,1,0,0,0,1,0},{0,1,1,1,1,0,0,0,1,0,0,0,0,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,0,1,0,0,0,1,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,0},{0,0,0,1,1,1,0,0,0,1,0,0,1,1,0,0,1,1,0,1,1,0,0,0,0,0,1,1,0,1,0,0,1,1,1,0,0,0,1,1,1,1,0,0,1,0,0,1,0,1},{0,0,1,0,0,0,1,0,0,1,1,1,1,0,0,0,0,1,0,0,1,0,1,1,1,0,0,1,0,0,1,1,1,1,0,1,1,0,1,1,1,0,0,0,0,1,1,1,1,0},{1,1,0,0,1,0,1,0,1,1,0,1,0,1,1,0,1,1,1,1,1,1,0,0,0,0,0,1,1,1,0,1,0,0,0,0,1,1,1,1,1,1,0,0,0,1,0,0,1,1},{1,0,1,0,1,0,0,0,0,0,1,1,1,1,0,0,1,1,1,1,0,1,0,1,1,1,0,0,0,1,0,0,0,0,0,0,1,1,0,1,1,1,0,1,0,0,0,1,1,0}}, {{65}},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            int[][] grid = inputs[2 * i];
            String inputStr = Matrix.printMatrix (grid);
            int ans = inputs[2 * i + 1][0][0];
            System.out.println (Printer.separator ());
            int output = tester.numDistinctIslands (grid);
            System.out.printf ("%s -> %s, expected: %d\n",
                inputStr, Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
            );
        }
    }
}

题目看起来找island用DFS找很简单, 不过怎么决定distinct? 设计一个合适的hash scheme应该是这一题的难点;

如果两个island是same, 那么意思就是两者有相同数量的点, 然后每一个点之间相差相同的向量; 实际上也就是一个平移关系. 那么在程序上, 你怎么表达这个关系?

我想到的一个办法是, 都移动到一个基准点, 比如都移动到[0][0]点的附近, 然后再比较; 感觉应该型;

好不容易最后还是AC了, 但是速度是212ms (1%), 这个说明我的思路还是有问题的;

string hash safest hash

首先, 在debug的时候发现, 我这个平移的思路还是对的, 但是我hash的计算方式, 并没有我想象的那么简单; 我一开始认为只要组成一个weighted sum这样正常的方式计算hash就行了, 比如给size_of_island, x, y分别以10000, 1000, 0的weight计算一个和就行了, 但是后面有非常大的case能够break掉这种hash的计算方式; 所以最后没有办法, 只能用最保险的hash计算方式, 也就是直接构造一个string;

虽然最后AC了, 但是这个方法看起来还是有明显的问题的, 不知道更好的方法到底在哪里有改进;

看了一下editorial, 没理由我之前的integer hash不能成功啊? 我决定再试一次; 首先, 这个是我AC的版本, 用的是string hash, 很慢: 

class Solution {  
    static int[][] increments = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  

    public int numDistinctIslands(int[][] grid) {  
        Set<String> islands = new HashSet<> ();  
        Set<int[]> set = new HashSet<> ();  
        int[] tl;  
        for (int i = 0; i < grid.length; i++) {  
            for (int j = 0; j < grid[0].length; j++) {  
                set.clear ();  
                tl = new int[]{51, 51};  
                dfs (i, j, grid, set, tl);  
                if (set.size () > 0)  
                    islands.add (hashCoordinates (set, tl, grid));  
            }  
        }  
        return islands.size ();  
    }  

    void dfs (int x, int y, int[][] grid, Set<int[]> set, int[] tl) {  
        if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] <= 0)  
            return;  
        grid[x][y] = -1;  
        if (x < tl[0])  
            tl[0] = x;  
        if (y < tl[1])  
            tl[1] = y;  
        set.add (new int[]{x, y});  
        for (int[] increment : increments)  
            dfs (x + increment[0], y + increment[1], grid, set, tl);  
    }  

    String hashCoordinates (Set<int[]> xys, int[] tl, int[][] grid) {  
        StringBuilder sb = new StringBuilder ();  
        for (int i = 0; i < grid.length; i++) {  
            for (int j = 0; j < grid[0].length; j++) {  
                sb.append ('0');  
            }  
        }  
        for (int[] xy : xys) {  
            int x = xy[0] - tl[0], y = xy[1] - tl[1];  
            sb.setCharAt (x * grid[0].length + y, '1');  
        }  
        return sb.toString ();  
    }  
}

editorial

Approach #1: Hash By Local Coordinates [Accepted]

Intuition and Algorithm

At the beginning, we need to find every island, which we can do using a straightforward depth-first search. The hard part is deciding whether two islands are the same.

Since two islands are the same if one can be translated to match another, let's translate every island so the top-left corner is (0, 0) For example, if an island is made from squares [(2, 3), (2, 4), (3, 4)], we can think of this shape as [(0, 0), (0, 1), (1, 1)] when anchored at the top-left corner.

From there, we only need to check how many unique shapes there ignoring permutations (so [(0, 0), (0, 1)] is the same as [(0, 1), (1, 0)]). We use sets directly as we have showcased below, but we could have also sorted each list and put those sorted lists in our set structure shapes.

In the Java solution, we converted our tuples (r - r0, c - c0) to integers. We multiplied the number of rows by 2 * grid[0].length instead of grid[0].length because our local row-coordinate could be negative. 

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();  
    }  
}

凭什么他的数字hash就能成功? 我在上面把我自己的一开始的integer hash的版本重新改了一下, 一个关键点就是给x的weight一定要是C! 而不是自己随便选一个大的prime什么的, 不如C最靠谱.

但是即使是这样, 最后还是挂掉了最后一个大case; 难道我这个求和的hash方案注定不行? 就必须要用他的hash of hashsets这样?

试了一下, 求product也不行, 无语了;

另外, 注意他这里的r0, c0的选择, 其实是每一个connected component的起点; 他这里用这个方法, 其实是有点默认利用了下面editorial2的那个path性质; 这个也是为什么他认为他这里算出来的这个差值有可能是负值;

Approach #2: Hash By Path Signature [Accepted]

Intuition and Algorithm

When we start a depth-first search on the top-left square of some island, the path taken by our depth-first search will be the same if and only if the shape is the same. We can exploit this by recording the path we take as our shape - keeping in mind to record both when we enter and when we exit the function. The rest of the code remains as in Approach #1.

这个思路相当的聪明嗨. 深刻理解了DFS的行为, 所以注意到了path之间的一致性; 

class Solution {  
    int[][] grid;  
    boolean[][] seen;  
    ArrayList<Integer> shape;  

    public void explore(int r, int c, int di) {  
        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(di);  
            explore(r+1, c, 1);  
            explore(r-1, c, 2);  
            explore(r, c+1, 3);  
            explore(r, c-1, 4);  
            shape.add(0);  
        }  
    }  
    public int numDistinctIslands(int[][] grid) {  
        this.grid = grid;  
        seen = new boolean[grid.length][grid[0].length];  
        Set shapes = new HashSet<ArrayList<Integer>>();  

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

        return shapes.size();  
    }  
}

但是他这里依然是依赖于一个HashSet来代表一个shape; 这俄格我现在学了倒是无所谓了, 不过我并不太理解为什么这个行得通; 我还以为这个题目的主要难点就是当你获得了一个island的所有的点之后, 你要自己给这个island计算一个hash出来, 但是这里看来, 他直接就借用HashSet自带的hash功能, 这样一个做法可以拓展到其他的题目上面去吗?

path is the aggregate of steps

他用每一个数字代表一个one move in one direction, 这样这些move组合起来就是一个path; 这个是一个很深刻的理解; 这样的一个理解最后也使得他这个解法的复杂度非常有利;

我想了一下, 我计算string hash的时候, 是把整个grid都画出来了; 能不能直接就把坐标本身(平移之后的)给扔到一个string里面去? 这个想法是可以的, 但是我自己的实现那样不行, 因为set不保证顺序, 除非跟他那样, 在DFS的时候直接就丢进去, 保留DFS的order, 但是这个又很麻烦, 因为在DFS的时候我还不知道要平移多少;

或者另外一个办法就是在我有set之后, 自己sort一下; 但是这样对时间复杂度就非常的不友好了;

总体来说他的editorial2真的就是很聪明;

discussion最优解: 

class Solution {  
    private static int[][] delta = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };  

    public int numDistinctIslands(int[][] grid) {  
        int m = grid.length, n = grid[0].length;  
        Set<List<List<Integer>>> islands = 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))  
                    islands.add(island);  
            }  
        }  
        return islands.size();  
    }  

    private boolean dfs(int i0, int j0, int i, int j, int[][] grid, int m, int n, List<List<Integer>> island) {  
        if (i < 0 || m <= i || j < 0 || n <= j || grid[i][j] <= 0) return false;  
        island.add(Arrays.asList(i - i0, j - j0));  
        grid[i][j] *= -1;  
        for (int d = 0; d < 4; d++) {  
            dfs(i0, j0, i + delta[d][0], j + delta[d][1], grid, m, n, island);  
        }  
        return true;  
    }  
}

其实还是很类似的, 利用了hash of collection的技巧;

discussion另外一个解法: 

class Solution {  

    int[][] dirs= new int[][]{{1,0},{0,1},{-1,0},{0,-1}};  
    public int numDistinctIslands(int[][] grid) {  
         Set<String> set= new HashSet<>();  
        int res=0;  

        for(int i=0;i<grid.length;i++){  
            for(int j=0;j<grid[0].length;j++){  
                if(grid[i][j]==1) {  
                    StringBuilder sb= new StringBuilder();  
                    helper(grid,i,j,0,0, sb);  
                    String s=sb.toString();  
                    if(!set.contains(s)){  
                        res++;  
                        set.add(s);  
                    }  
                }  
            }  
        }  
        return res;  
    }  

    public  void helper(int[][] grid,int i,int j, int xpos, int ypos,StringBuilder sb){  
        grid[i][j]=0;  
        sb.append(xpos+""+ypos);  
        for(int[] dir : dirs){  
            int x=i+dir[0];  
            int y=j+dir[1];  
            if(x<0 || y<0 || x>=grid.length || y>=grid[0].length || grid[x][y]==0) continue;  
            helper(grid,x,y,xpos+dir[0],ypos+dir[1],sb);  
        }  
    }  
}

不过这个人在写这个解法的时候其实是已经无意识的用到了path uniqueness这个性质了, 不然很难说按顺序把每一个点的坐标连起来, 就能够唯一对应一个shape (也就是两个same的shape能得到相同的string的原因就是因为他们有相同的path而已);

一个分析:

@yangshun said in Simple Python 169ms:

This question is very similar to the Max Area of Island question but here instead of counting the area for each island, we find out the shape of each island.

The shape of the island can be represented by taking the relative position of the connected cells from the leftmost cell on the top row of the island (the first cell of each island we will visit). For each island we visit, we are guaranteed to visit the top row's leftmost cell first if we iterate the matrix row by row, left to right direction. We will get the same order of cells for islands of the same shape if we perform the search in a consistent manner.

所以在这种grid问题里面DFS的order也是要熟悉的一个内容;

至少如果再被问到shape相关的问题, 要能够想到转换成dfs visiting order来做;

submission最优解: 45(95) 

class Solution {  
    public int numDistinctIslands(int[][] grid) {  
        int row=grid.length;  
        if(row==0) return 0;  
        int col=grid[0].length;  
        if(col==0) return 0;  
        HashSet<String> islands = new HashSet<>();  
        for(int i=0; i<row; i++){  
            for(int j=0; j<col; j++){  
                if(grid[i][j]==1){  
                    StringBuilder route = new StringBuilder();  
                    String direction = "";  
                    dfs(grid, i, j, route, direction);  
                    islands.add(route.toString());  
                }          
            }  
        }  
        return islands.size();  
    }  

    private void dfs(int[][] grid, int x, int y, StringBuilder route, String direction){  
        if(x<0 || x>=grid.length || y<0 || y>=grid[0].length || grid[x][y]!=1) return;  

        route.append(direction);  
        grid[x][y]=0;  
        dfs(grid, x-1, y, route, "u");  
        //route.append("1");  
        dfs(grid, x+1, y, route, "d");  
        //route.append("2");  
        dfs(grid, x, y+1, route, "r");  
        //route.append("3");  
        dfs(grid, x, y-1, route, "l");  
        route.append("b"); // 必要的，如果没有，就容易混起来同一轮的两个方向。一定要加区分符了对于每一轮！！  
    }  
}

基本还是记录move的方法, 注意看他的comment, 尤其是最后一行的这个comment, 这个好像editorial里面忘记提到了;

Problem Description

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.

Difficulty:Medium
Total Accepted:5.3K
Total Submissions:11.7K
Contributor:1337c0d3r
Companies
amazon
Related Topics
hash tabledepth-first search
Similar Questions
Number of IslandsNumber of Distinct Islands II

results matching ""

    No results matching ""