0694. Number of Distinct Islands

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

Description

You are given an m x n binary matrix grid. 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.

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.

Return the number of distinct islands.

Example 1:

**Input:** grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]
**Output:** 1

Example 2:

**Input:** grid = [[1,1,0,1,1],[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]]
**Output:** 3

Constraints:

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 50

• grid[i][j] is either 0 or 1.

ac

class Solution {
    int[][] dirs = new int[][]{{0, 1},{0, -1},{1, 0}, {-1, 0}};
    public int numDistinctIslands(int[][] grid) {
        int row = grid.length, col = grid[0].length;
        Set<String> set = new HashSet<>();
        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                if (grid[r][c] == 1) {
                    StringBuilder sb = new StringBuilder();
                    dfs(grid, r, c, r, c, sb);
                    set.add(sb.toString());
                }
            }
        }

        return set.size();
    }

    public void dfs(int[][] grid, int r0, int c0, int r, int c, StringBuilder sb) {
        // exit
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == 0) return;

        sb.append((r - r0) + "-" + (c - c0) + "#");
        grid[r][c] = 0;
        for (int[] d : dirs) {
            int r2 = r + d[0];
            int c2 = c + d[1];
            dfs(grid, r0, c0, r2, c2, sb);
        }
    }
}

/*
DFS find eachh region. 1) when meet 1, go into DFS, calculate distance of each point to start point; 2) put each point in string format
*/