Similar Idea to "Number of Islands", Easy to Understand


  • 0

    Use [0, 1, 2, 3] to store every direction, and use another mark * to represent the end of all DFS to avoid some cases.

    class Solution {
        public int numDistinctIslands(int[][] grid) {
            if(grid == null || grid.length == 0 || grid[0].length == 0) return 0;
            Set<String> set = new HashSet<String>();
            for(int i = 0; i < grid.length; ++i) {
                for(int j = 0; j < grid[0].length; ++j) {
                    if(grid[i][j] == 1) {
                        StringBuilder path = new StringBuilder();
                        dfs(grid, i, j, path);
                        String s = path.toString();
                        set.add(s);
                    }
                }
            }
            return set.size();
        }
        private int[][] dir = {{1, 0},{0, 1},{-1, 0},{0, -1}};
        private void dfs(int[][] grid, int i, int j, StringBuilder path) {
            grid[i][j] = 0;
            for (int k = 0; k < 4; k++) {
                if (isValid(grid, i + dir[k][0], j + dir[k][1])) {
                    path.append(k);
                    dfs(grid, i + dir[k][0], j + dir[k][1], path);
                }
            } 
            path.append("*");
        }
        private boolean isValid(int[][] grid, int i, int j) {
            return i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && grid[i][j] == 1;
        }
    }
    

Log in to reply
 

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