Skip to content

694. Number of Distinct Islands

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:

img

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:

img

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.

Solution:

BFS

class Solution {
    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public int numDistinctIslands(int[][] grid) {
        if (grid == null || grid.length == 0){
            return 0;
        }

        int n = grid.length;
        int m = grid[0].length;

        Set<String> distinctIslands = new HashSet<>();

        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if (grid[i][j] == 1){
                    List<String> shape = new ArrayList<String>();
                    bfs(grid, i, j, shape);
                    distinctIslands.add(String.join(",", shape));

                }
            }
        }

        return distinctIslands.size();

    }


    private void bfs(int[][] grid, int x, int y, List<String> shape){
        int n = grid.length;
        int m = grid[0].length;

        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{x, y});

        grid[x][y] = 0;

        shape.add("0,0");

        while(!queue.isEmpty()){
            int[] cur = queue.poll();
            int curX = cur[0];
            int curY = cur[1];

            for (int[] dir : dirs){
                int newX = curX + dir[0];
                int newY = curY + dir[1];

                if (newX >= 0 && newX < n && newY >= 0 && newY < m && grid[newX][newY] == 1){
                    queue.offer(new int[]{newX, newY});
                    grid[newX][newY] = 0;
                    String newString = (newX - x) + "," + (newY - y);
                    shape.add(newString);
                }
            }
        }


    }
}

// TC: O(n*m)
// SC: O(n*m)

DFS

import java.util.*;

class Solution {
    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 四个方向：右、左、下、上

    public int numDistinctIslands(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int n = grid.length;
        int m = grid[0].length;

        Set<String> distinctIslands = new HashSet<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    List<String> shape = new ArrayList<>();
                    dfs(grid, i, j, i, j, shape);  // 使用 DFS 来记录形状
                    distinctIslands.add(String.join(",", shape));  // 将形状存储为字符串，加入集合
                }
            }
        }

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

    private void dfs(int[][] grid, int x, int y, int baseX, int baseY, List<String> shape) {
        int n = grid.length;
        int m = grid[0].length;

        // 记录当前单元格的相对位置
        shape.add((x - baseX) + "," + (y - baseY));

        // 标记当前单元格为已访问（将 1 变为 0）
        grid[x][y] = 0;

        // 向四个方向进行 DFS
        for (int[] dir : dirs) {
            int newX = x + dir[0];
            int newY = y + dir[1];

            // 如果新位置在界内且是陆地，则继续进行 DFS
            if (newX >= 0 && newX < n && newY >= 0 && newY < m && grid[newX][newY] == 1) {
                dfs(grid, newX, newY, baseX, baseY, shape);
            }
        }
    }
}

// TC: O(n*m)
// SC: O(n*m)