711. Number of Distinct Islands II

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.

Solution:

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

    // 创建8个列表分别存储每个岛屿的8种变换后的形状
    private List<Integer[]> shape1 = new ArrayList<>();
    private List<Integer[]> shape2 = new ArrayList<>();
    private List<Integer[]> shape3 = new ArrayList<>();
    private List<Integer[]> shape4 = new ArrayList<>();
    private List<Integer[]> shape5 = new ArrayList<>();
    private List<Integer[]> shape6 = new ArrayList<>();
    private List<Integer[]> shape7 = new ArrayList<>();
    private List<Integer[]> shape8 = new ArrayList<>();

    public int numDistinctIslands2(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        Set<String> uniqueIslands = new HashSet<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    List<int[]> shape = new ArrayList<>();
                    dfs(grid, i, j, shape, i, j);  // 使用DFS找到岛屿的形状

                    String normalizedShape = normalize(shape);  // 标准化形状
                    uniqueIslands.add(normalizedShape);  // 添加到集合中，自动去重

                    // 清空列表，准备处理下一个岛屿
                    clearTransformationLists();
                }
            }
        }

        return uniqueIslands.size();  // 返回不同形状的岛屿数量
    }

    // 深度优先搜索（DFS）查找岛屿
    private void dfs(int[][] grid, int i, int j, List<int[]> shape, int baseRow, int baseCol) {
        grid[i][j] = -1;  // 标记为已访问
        shape.add(new int[]{i - baseRow, j - baseCol});  // 记录相对坐标

        for (int[] dir : DIRECTIONS) {
            int newRow = i + dir[0];
            int newCol = j + dir[1];

            if (newRow >= 0 && newRow < grid.length && newCol >= 0 && newCol < grid[0].length && grid[newRow][newCol] == 1) {
                dfs(grid, newRow, newCol, shape, baseRow, baseCol);  // 继续深度搜索
            }
        }
    }

    // 生成8种变换，并选择最小字典序的形状作为标准化后的形状
    private String normalize(List<int[]> shape) {
        for (int[] point : shape) {
            int x = point[0];
            int y = point[1];

            // 将变换后的坐标分别存储到不同的列表中
            shape1.add(new Integer[]{x, y});         // 原始形状
            shape2.add(new Integer[]{x, -y});        // 沿y轴镜像
            shape3.add(new Integer[]{-x, y});        // 沿x轴镜像
            shape4.add(new Integer[]{-x, -y});       // 沿x、y轴镜像
            shape5.add(new Integer[]{y, x});         // 顺时针旋转90度
            shape6.add(new Integer[]{y, -x});        // 旋转90度并镜像
            shape7.add(new Integer[]{-y, x});        // 逆时针旋转270度
            shape8.add(new Integer[]{-y, -x});       // 逆时针旋转270度并镜像
        }

        // 对每种形状进行标准化
        String normalizedShape1 = convertToNormalizedString(shape1);
        String normalizedShape2 = convertToNormalizedString(shape2);
        String normalizedShape3 = convertToNormalizedString(shape3);
        String normalizedShape4 = convertToNormalizedString(shape4);
        String normalizedShape5 = convertToNormalizedString(shape5);
        String normalizedShape6 = convertToNormalizedString(shape6);
        String normalizedShape7 = convertToNormalizedString(shape7);
        String normalizedShape8 = convertToNormalizedString(shape8);

        // 将所有形状存入列表并排序，选择最小字典序的形状
        List<String> normalizedShapes = Arrays.asList(normalizedShape1, normalizedShape2, normalizedShape3, 
                                                      normalizedShape4, normalizedShape5, normalizedShape6,
                                                      normalizedShape7, normalizedShape8);

        Collections.sort(normalizedShapes);
        return normalizedShapes.get(0);  // 返回最小字典序的形状
    }

    // 将形状转换为标准化后的字符串
    private String convertToNormalizedString(List<Integer[]> shape) {
        // 对形状按坐标排序
        Collections.sort(shape, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);

        // 将坐标平移到左上角
        int baseX = shape.get(0)[0], baseY = shape.get(0)[1];
        StringBuilder sb = new StringBuilder();
        for (Integer[] point : shape) {
            sb.append((point[0] - baseX) + "," + (point[1] - baseY) + " ");
        }
        return sb.toString().trim();
    }

    // 清空所有变换列表
    private void clearTransformationLists() {
        shape1.clear();
        shape2.clear();
        shape3.clear();
        shape4.clear();
        shape5.clear();
        shape6.clear();
        shape7.clear();
        shape8.clear();
    }
}

?????