Sad C Solution, will try other HLLs


  • 0
    R
    typedef struct stack {
        int i[1000];
        int j[1000];
        int len;
    } stack_t;
    
    void stack_init(stack_t *s) {
        s->len = -1;
    }
    
    bool stack_check(stack_t *s) {
        if (s->len >= 0) {
            return (true);
        }
        
        return (false);
    }
    
    void stack_pop(stack_t *s, int *i, int *j) {
        if (s->len == -1) {
            return;
        }
        
        int last = s->len;
        *i = (s->i)[last];
        *j = (s->j)[last];
        s->len--;
    }
    
    void stack_push(stack_t *s, int i, int j) {
        if (s->len == 1000) {
            return;
        }
        s->len++;
        (s->i)[s->len] = i;
        (s->j)[s->len] = j;
    }
    
    void explore (char **grid, int i, int j, int gridRowSize, int gridColSize,
        int ***numIslandsPtr, int *islandIdx) {
        stack_t s;
        int **numIslands = *(numIslandsPtr);
        
        if (numIslands[i][j] != -1) {
            return;
        }
    
        stack_init(&s);
        stack_push(&s, i, j);
    
        while (stack_check(&s)) {
            stack_pop(&s, &i, &j);
            if (numIslands[i][j] != -1)
                continue;
            
            numIslands[i][j] = *islandIdx;
            if ((i >= 1) && (grid[i-1][j] == '1'))
                stack_push(&s, i-1, j);
            
            if ((j >= 1) && (grid[i][j-1] == '1'))
                stack_push(&s, i, j-1);
    
            if ((j < (gridColSize-1)) && (grid[i][j+1] == '1'))
                stack_push(&s, i, j+1);
    
            if ((i < (gridRowSize -1)) && (grid[i+1][j] == '1'))
                stack_push(&s, i+1, j);
        }
        
        (*islandIdx)++;
    }
    
    int numIslands(char** grid, int gridRowSize, int gridColSize) {
        int **numIslands = (int **)malloc(sizeof(int*)*gridRowSize);
        int i = 0, j = 0;
        int islandIdx = 0;
        for (i = 0; i < gridRowSize; i++) {
            numIslands[i] = (int *)malloc(sizeof(int)*gridColSize);
        }
        
        for (i = 0; i < gridRowSize; i++) {
            for (j = 0; j < gridColSize; j++) {
                numIslands[i][j] = -1;
            }
        }
        
        for (i = 0; i < gridRowSize; i++) {
            for (j = 0; j < gridColSize; j++) {
                if (grid[i][j] == '1')
                    explore(grid, i, j, gridRowSize, gridColSize, &numIslands, &islandIdx);
            }
        }
        
        for (i = 0; i < gridRowSize; i++) {
            free(numIslands[i]);
        }
        free(numIslands);
        return (islandIdx);
    }
    

Log in to reply
 

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