Number of Distinct Islands

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <vector>
#include <set>
using namespace std;
class Solution {
public:
    void dfs(vector<vector<int>>& grid, int x, int y, int baseX, int baseY, vector<pair<int,int>>& shape) {
        int m = grid.size(), n = grid[0].size();
        if (x<0||y<0||x>=m||y>=n||grid[x][y]==0) return;
        grid[x][y]=0;
        shape.push_back({x-baseX, y-baseY});
        dfs(grid,x+1,y,baseX,baseY,shape);
        dfs(grid,x-1,y,baseX,baseY,shape);
        dfs(grid,x,y+1,baseX,baseY,shape);
        dfs(grid,x,y-1,baseX,baseY,shape);
    }
    int numDistinctIslands(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        set<vector<pair<int,int>>> shapes;
        for (int i=0;i<m;++i) for (int j=0;j<n;++j) if (grid[i][j]) {
            vector<pair<int,int>> shape;
            dfs(grid,i,j,i,j,shape);
            shapes.insert(shape);
        }
        return shapes.size();
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func numDistinctIslands(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    shapes := map[string]struct{}{}
    var dfs func(x, y, baseX, baseY int, shape *[]string)
    dfs = func(x, y, baseX, baseY int, shape *[]string) {
        if x<0||y<0||x>=m||y>=n||grid[x][y]==0 { return }
        grid[x][y]=0
        *shape = append(*shape, fmt.Sprintf("%d_%d", x-baseX, y-baseY))
        dfs(x+1,y,baseX,baseY,shape)
        dfs(x-1,y,baseX,baseY,shape)
        dfs(x,y+1,baseX,baseY,shape)
        dfs(x,y-1,baseX,baseY,shape)
    }
    for i:=0;i<m;i++ { for j:=0;j<n;j++ { if grid[i][j]==1 {
        shape := []string{}
        dfs(i,j,i,j,&shape)
        key := strings.Join(shape, ",")
        shapes[key]=struct{}{}
    }}}
    return len(shapes)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import java.util.*;
class Solution {
    public int numDistinctIslands(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        Set<String> shapes = new HashSet<>();
        for (int i=0;i<m;i++) for (int j=0;j<n;j++) if (grid[i][j]==1) {
            List<String> shape = new ArrayList<>();
            dfs(grid,i,j,i,j,shape);
            shapes.add(String.join(",", shape));
        }
        return shapes.size();
    }
    void dfs(int[][] grid, int x, int y, int baseX, int baseY, List<String> shape) {
        int m = grid.length, n = grid[0].length;
        if (x<0||y<0||x>=m||y>=n||grid[x][y]==0) return;
        grid[x][y]=0;
        shape.add((x-baseX)+"_"+(y-baseY));
        dfs(grid,x+1,y,baseX,baseY,shape);
        dfs(grid,x-1,y,baseX,baseY,shape);
        dfs(grid,x,y+1,baseX,baseY,shape);
        dfs(grid,x,y-1,baseX,baseY,shape);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun numDistinctIslands(grid: Array<IntArray>): Int {
        val m = grid.size; val n = grid[0].size
        val shapes = mutableSetOf<String>()
        fun dfs(x: Int, y: Int, baseX: Int, baseY: Int, shape: MutableList<String>) {
            if (x<0||y<0||x>=m||y>=n||grid[x][y]==0) return
            grid[x][y]=0
            shape.add("${x-baseX}_${y-baseY}")
            dfs(x+1,y,baseX,baseY,shape)
            dfs(x-1,y,baseX,baseY,shape)
            dfs(x,y+1,baseX,baseY,shape)
            dfs(x,y-1,baseX,baseY,shape)
        }
        for (i in 0 until m) for (j in 0 until n) if (grid[i][j]==1) {
            val shape = mutableListOf<String>()
            dfs(i,j,i,j,shape)
            shapes.add(shape.joinToString(","))
        }
        return shapes.size
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def numDistinctIslands(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        shapes = set()
        def dfs(x, y, baseX, baseY, shape):
            if x<0 or y<0 or x>=m or y>=n or grid[x][y]==0: return
            grid[x][y]=0
            shape.append((x-baseX, y-baseY))
            dfs(x+1,y,baseX,baseY,shape)
            dfs(x-1,y,baseX,baseY,shape)
            dfs(x,y+1,baseX,baseY,shape)
            dfs(x,y-1,baseX,baseY,shape)
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    shape = []
                    dfs(i,j,i,j,shape)
                    shapes.add(tuple(shape))
        return len(shapes)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

use std::collections::HashSet;
impl Solution {
    pub fn num_distinct_islands(grid: Vec<Vec<i32>>) -> i32 {
        let m = grid.len(); let n = grid[0].len();
        let mut grid = grid;
        let mut shapes = HashSet::new();
        fn dfs(grid: &mut Vec<Vec<i32>>, x: i32, y: i32, base_x: i32, base_y: i32, shape: &mut Vec<(i32,i32)>) {
            let m = grid.len() as i32; let n = grid[0].len() as i32;
            if x<0||y<0||x>=m||y>=n||grid[x as usize][y as usize]==0 { return; }
            grid[x as usize][y as usize]=0;
            shape.push((x-base_x, y-base_y));
            dfs(grid,x+1,y,base_x,base_y,shape);
            dfs(grid,x-1,y,base_x,base_y,shape);
            dfs(grid,x,y+1,base_x,base_y,shape);
            dfs(grid,x,y-1,base_x,base_y,shape);
        }
        for i in 0..m as i32 {
            for j in 0..n as i32 {
                if grid[i as usize][j as usize]==1 {
                    let mut shape = vec![];
                    dfs(&mut grid,i,j,i,j,&mut shape);
                    shapes.insert(shape);
                }
            }
        }
        shapes.len() as i32
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

function numDistinctIslands(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    const shapes = new Set<string>();
    function dfs(x: number, y: number, baseX: number, baseY: number, shape: string[]) {
        if (x<0||y<0||x>=m||y>=n||grid[x][y]==0) return;
        grid[x][y]=0;
        shape.push(`${x-baseX}_${y-baseY}`);
        dfs(x+1,y,baseX,baseY,shape);
        dfs(x-1,y,baseX,baseY,shape);
        dfs(x,y+1,baseX,baseY,shape);
        dfs(x,y-1,baseX,baseY,shape);
    }
    for (let i=0;i<m;i++) for (let j=0;j<n;j++) if (grid[i][j]==1) {
        const shape: string[] = [];
        dfs(i,j,i,j,shape);
        shapes.add(shape.join(","));
    }
    return shapes.size;
}