711. Number of Distinct Islands II

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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 they have the same shape, or have the same shape after rotation (90, 180, or 270 degrees only) or reflection (left/right direction or up/down direction).

Return the number of distinct islands.

Example 1:

Input: grid = [[1,1,0,0,0],[1,0,0,0,0],[0,0,0,0,1],[0,0,0,1,1]]
Output: 1
Explanation: The two islands are considered the same because if we make a 180 degrees clockwise rotation on the first island, then two islands will have the same shapes.

Example 2:

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

Constraints:

• $m == grid.length$
• $n == grid[i].length$
• $1 <= m, n <= 50$
• $grid[i][j]$ is either 0 or 1.

Code

class Solution {
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int[][] trans = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

    public int numDistinctIslands2(int[][] grid) {
        Set<String> islands = new HashSet<>();

        for (int i = 0; i < grid.length; i++){
            for (int j = 0; j < grid[0].length; j++){
                if (grid[i][j] == 1){
                    List<int[]> cells = new ArrayList<>();
                    dfs(grid, i, j, cells);
                    String key = norm(cells);
                    islands.add(key);
                }
            }
        }

        return islands.size();
    }

    private void dfs(int[][] grid, int i, int j, List<int[]> cells){
        // 放入当前island的所有节点坐标
        cells.add(new int[]{i, j});
        grid[i][j] = 0;

        for (int[] dir : dirs){
            int x = i + dir[0];
            int y = j + dir[1];

            if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == 0)
            continue;

            dfs(grid, x, y, cells);
        }
    }

    private String norm(List<int[]> cells){
        List<String> forms = new ArrayList<>();
        // generate 8 different transformations
        // (x, y), (x, -y), (-x, y), (-x, -y)
        // (y, x), (-y, x), (y, -x), (-y, -x)
        for (int[] ts : trans){
            List<int[]> list1 = new ArrayList<>();
            List<int[]> list2 = new ArrayList<>();

            for (int[] cell : cells){
                list1.add(new int[]{cell[0] * ts[0], cell[1] * ts[1]});
                list2.add(new int[]{cell[1] * ts[1], cell[0] * ts[0]});
            }

            forms.add(getKey(list1));
            forms.add(getKey(list2));
        }

        // sort the keys: take the first one as the representative key
        Collections.sort(forms);
        return forms.get(0);
    }

    private String getKey(List<int[]>cells){
        // sort the cells before generate the key
        Collections.sort(cells, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                if (a[0] != b[0]){
                    return a[0] - b[0];
                }else{
                    return a[1] - b[1];
                }
            }
        });

        StringBuilder sb = new StringBuilder();
        int x = cells.get(0)[0];
        int y = cells.get(0)[1];

        for (int[] cell : cells) {
            sb.append((cell[0] - x) + ":" + (cell[1] - y) + ":");
        }

        return sb.toString();
    }
}