C solution, DFS + TrieTree, simple but effective

• Use DFS to find islands, meanwhile maintaining a TrieTree to record the search-path. Each node in the TrieTree has 5 choices meaning next search step (left, right, up, down, back). Once a new node is added to the TrieTree, a distinct island is found.

``````// organize the dfs searched path as a tree, like TrieTree.
struct step {
// 5 action at each step: left, right, up, down, back
struct step *next[5];
};

struct step *dfs(int **grid, int m, int n, int i, int j, struct step *s, int *newIsland) {
grid[i][j] = 0;
int dr[5] = {0, 0, -1, 1, 0};
int dc[5] = {-1, 1, 0, 0, 0};
int r, c, k;
for (k = 0; k < 5; k++) {
r = i + dr[k];
c = j + dc[k];
if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] || k == 4) {
if (s->next[k] == NULL) {
// new node added to path-tree, meaning new island found.
(*newIsland)++;
s->next[k] = (struct step *) calloc(1, sizeof(struct step));
}
if (k < 4) {
s = dfs(grid, m, n, r, c, s->next[k], newIsland);
} else {
s = s->next[4];
}
}
}
return s;
}

int numDistinctIslands(int** grid, int gridRowSize, int gridColSize) {
int i, j, cntIslands = 0;
struct step *s = (struct step *) calloc(1, sizeof(struct step));

for (i = 0; i < gridRowSize; i++) {
for (j = 0; j < gridColSize; j++) {
if (grid[i][j]) {
int newIsland = 0;
dfs(grid, gridRowSize, gridColSize, i, j, s, &newIsland);
cntIslands += newIsland ? 1 : 0;
}
}
}
return cntIslands;
}
``````

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