C, 3mS, Stack + DFS


  • 0
    M

    Recursive implementation throws a runtime error, it's probably a call stack overflow. So here is an iterative solution. Instead of function call stack let's utilize the stack data structure.

    A simple a two step solution:

    1. First locate and tag ('T') all the 'O' cells accessible from the boundary of the board by running a DFS scan on all the four sides.
    2. Next, revert the tagged cells ('T') to 'O' and change all the remaining 'O' cells to 'X'.
    /******************************************/
    /* Data Structure                         */
    /******************************************/
    struct ch_pos
    {
        int r;
        int c;
    };
    
    void ResetO(char** b, int bRSz, int bCSz, int r, int c, void *stack)
    {
        struct ch_pos pos;
    
        /* If the value at the location is not 'O', then return. */
        if ((b[r])[c] != 'O') return;
    
        /* Push the element to the stack */
        pos = (struct ch_pos){r, c};
        if (StackPush(stack, &pos)) return;
    
        /* Process all the stack elements */
        while (!StackPop(stack, &pos)) {
            (b[pos.r])[pos.c] = 'T';
    
            /* Attempt to push the neighboring cell on the next row */
            if ((++pos.r < bRSz) && (b[pos.r])[pos.c] == 'O')
                StackPush(stack, &pos);
            --pos.r;
    
            /* Attempt to push the neighboring cell on the same row */
            if ((++pos.c < bCSz) && (b[pos.r])[pos.c] == 'O')
                StackPush(stack, &pos);
            --pos.c;
    
            /* Attempt to push the neighboring cell on the same row */
            if ((--pos.c >= 0) && (b[pos.r])[pos.c] == 'O')
                StackPush(stack, &pos);
            ++pos.c;
    
            /* Attempt to push the neighboring cell on the previous row */
            if ((--pos.r >= 0) && (b[pos.r])[pos.c] == 'O')
                StackPush(stack, &pos);
        }
    }
    
    void solve(char** b, int bRSz, int bCSz)
    {
        int i, j;
        void *stack;
    
        /* Allocate stack  */
        if ((stack = StackAlloc(bRSz * bCSz, sizeof(struct ch_pos))) == NULL)
            return;
    
        /* Now run a boundary scan to figure out all the accessible 'O'
           cells. First scan top and bottom rows. */
        for (j = 0; j < bCSz; ++j) {
            ResetO(b, bRSz, bCSz, 0, j, stack);
            ResetO(b, bRSz, bCSz, bRSz - 1, j, stack);
        }
    
        /* Scan first and last column. */
        for (j = 1; j < bRSz - 1; ++j) {
            ResetO(b, bRSz, bCSz, j, 0, stack);
            ResetO(b, bRSz, bCSz, j, bCSz - 1, stack);
        }
    
        /* Revert 'T's to Os and make remaining 'O's as 'X's. */
        for (i = 0; i < bRSz; ++i)
            for (j = 0; j < bCSz; ++j)
                (b[i])[j] = (b[i])[j] == 'T' ? 'O' : 'X'; // Ts revert to Os
        StackFree(stack); //free
    }
    

Log in to reply
 

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