C solution, DFS + TrieTree, simple but effective


  • 0
    V

    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;
    }
    

Log in to reply
 

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