# Clean java solution (DFS)

• Not much difference with other DFS method.
To distinguish the shape of island, I use a string to encode visiting sequence.

``````class Solution {
int[][] dirs = {{-1,0},{0,-1},{1,0},{0,1}};
String s = "";
boolean[][] visited;
public int numDistinctIslands(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
HashSet<String> hs = new HashSet<>();
int m = grid.length;
int n = grid[0].length;
visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1 && !visited[i][j]) {
s = "";
dfs(grid, i, j, m, n, 0);
}
}
}
return hs.size();
}

private void dfs(int[][] grid, int i, int j, int m, int n, int mark) {
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0 || visited[i][j]) return;
visited[i][j] = true;
s += mark;//mark direction
for (int k = 0; k < 4; k++) {
dfs(grid, i + dirs[k][0], j + dirs[k][1], m, n, k + 1);
}
s += "-";//mark finishing current position
}
}
``````

• @lidaxia Could you help me understand the importance of the line

`` s += "-"; //mark finishing current position ``

Why we have to mark the finishing current position?

I thought recording DFS visiting direction for each island is good enough to determine the shape of the island. However without this line of code, some test cases' output will be off by 1.