Simple JAVA DFS


  • 0
    F

    Thanks for @alexander solution. Reference from him.

    class Solution {
        public int numDistinctIslands(int[][] grid) {
            Set<List<List<Integer>>> islands = new HashSet<>();
            int count = 0;
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (grid[i][j] == 1) {
                        List<List<Integer>> island = new ArrayList<>(); 
                        dfs(grid, i, j, i, j, island);
                        islands.add(island);
                    }
                }
            }
            return islands.size();
        }
        public void dfs(int[][] grid, int i, int j, int i0, int j0, List<List<Integer>> island) {
            if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != 1) {
                return;
            }
            grid[i][j] = -1;
            island.add(Arrays.asList(i - i0, j - j0));
            int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
            for (int[] d: dir) {
                dfs(grid, i + d[0], j + d[1], i0, j0, island);
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.