非常好的题; dfs的同时还要纪录dfs留下的痕迹；同时，因为dfs达到边缘之后要backtracking再找别的可能直到当前dfs完毕，并且用Stringdfs留下的痕迹表征形状, set自动去重; 可以说是dfs题目中的典范.

关键:

  1. dfs标准写法: 递归之前写terminal condition;
  2. 递归之后因为要回溯: 递归之后标明回溯的部分:
1
2
3
4
5
6
7
8
/** WARNING: DO NOT FORGET to add path for backtracking, otherwise, we may have same result when we count two 
 * distinct islands in some cases
 * 
 * eg:              1 1 1   and    1 1 0
 *                  0 1 0          0 1 1
 * with b:          rdbr           rdr
 * without b:       rdr            rdr
 * */
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
29
30
class Solution {
    private int m, n;
    
    public int numDistinctIslands(int[][] grid) {
        Set<String> set = new HashSet<>();
        if (grid == null || grid[0].length == 0) return 0;
        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) {
                    StringBuilder sb = new StringBuilder();
                    dfs(grid, i, j, sb, "o");
                    set.add(sb.toString());
                }
            }
        }
        return set.size();
    }
    
    public void dfs(int[][] grid, int i, int j, StringBuilder sb, String dir) {
        if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] == 0) return;
        sb.append(dir);
        grid[i][j] = 0;
        dfs(grid, i+1, j, sb, "r");
        dfs(grid, i-1, j, sb, "l");
        dfs(grid, i, j+1, sb, "u");
        dfs(grid, i, j-1, sb, "d");
        sb.append("b");
    }
}

来自于 LC200. Number of 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
class Solution {
    private int m, n;
    private int count = 0;
    
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        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') {
                    dfs(grid, i, j); 
                    count++;
                }
            }
        }
        return count;
    }
    
    public void dfs(char[][] grid, int i, int j) {
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') return;
        grid[i][j] = '0';
        dfs(grid, i-1, j); dfs(grid, i+1, j); dfs(grid, i, j-1); dfs(grid, i, j+1);
    }
}