# 0694. Number of Distinct Islands
###### tags: `Leetcode` `Bloomberg` `Medium` `DFS` `Island`
Link: https://leetcode.com/problems/number-of-distinct-islands/
## 思路
### BFS
为了防止下图的情况发生导致区分不开是不是形状一样
所以每次poll出来一个的时候不管它四个方向能不能继续走
都加'#'
### DFS
将走过的路径存成字符串，这里要注意的是由于是用DFS，所以以下三种情况产生的字符串是一样的（都是RDDDR)，因此为了做区分，每次退出一个dfs call的时候都在末尾补'0'
因为过程中要生成很多新的字符串，所以这题用递归比较简单，如果用stack写就会变复杂了

## Code
### BFS

class Solution {
    public int numDistinctIslands(int[][] grid) {
        Set<String> islands = new HashSet<>();
        int m = grid.length, n = grid[0].length;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j]==1){
                    islands.add(bfs(grid, i, j));
                }
            }
        }
        return islands.size();
    }
    private String bfs(int[][] grid, int x, int y){
        int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
        char[] dirChar = new char[]{'D', 'U', 'R', 'L'};
        StringBuilder sb = new StringBuilder();
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x,y});
        grid[x][y] = -1;
        while(!q.isEmpty()){
            int[] curr = q.poll();
            for(int i=0; i<dirs.length; i++){
                int newx = curr[0]+dirs[i][0];
                int newy = curr[1]+dirs[i][1];
                if(newx>=0 && newx<grid.length && newy>=0 && newy<grid[0].length && grid[newx][newy]==1){
                    q.add(new int[]{newx, newy});
                    grid[newx][newy] = -1;
                    sb.append(dirChar[i]);
                }
            }
            sb.append('#');
        }
        return sb.toString();
    }
}

### DFS

class Solution {
    Set<String> path;
    boolean[][] visited;
    StringBuffer currIsland;
    public int numDistinctIslands(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        path = new HashSet<>();
        visited = new boolean[m][n];
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(!visited[i][j] && grid[i][j]==1){
                    currIsland = new StringBuffer();
                    dfs(grid, i, j, '0');
                    if(currIsland.length() == 0){
                        continue;
                    }
                    path.add(currIsland.toString());
                }
            }
        }
        return path.size();
    }
    public void dfs(int[][] grid, int row, int col, char dir){
        if(row<0 || col<0 || row>=grid.length || col>=grid[0].length){
            return;
        }
        if(visited[row][col]||grid[row][col]==0) return;
        visited[row][col] = true;
        currIsland.append(dir);
        dfs(grid, row-1, col, 'U');
        dfs(grid, row+1, col, 'D');
        dfs(grid, row, col+1, 'R');
        dfs(grid, row, col-1, 'L');
        currIsland.append('0');
    }
}