# C, 3mS, Stack + DFS

• 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
}
``````

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