CODEWITHSUNDEEP
c++recursionflood-fill
Claypoolsbass
Claypoolsbass

Reputation:

Blob ...how to write non-recursively

I have written the following program, using recursion, but I can't figure out how to write it non-recursively. Every time I run my non-recursive version the numbers are way off. Any suggestions on how to write the following method without recursion?

int countCells(color grid[ROWS][COLS], int r, int c) {
 if (r < 0 || r >= ROWS || c < 0 || c >= COLS) {
   return 0;
 } else if (grid[r][c] != ABNORMAL) {
   return 0;
 } else {
   grid[r][c] = TEMPORARY;
   return 1
     + countCells(grid,r-1,c-1) + countCells(grid,r-1,c)
     + countCells(grid,r-1,c+1) + countCells(grid,r,c+1)
     + countCells(grid,r+1,c+1) + countCells(grid,r+1,c)
     + countCells(grid,r+1,c-1) + countCells(grid,r,c-1);
    }
}

This is what I have tried btw:

int countCells(color grid[ROWS][COLS], int r, int c)
{
  int temp = 0;
  if (r < 0 || r >= ROWS || c < 0 || c >= COLS)
  {
    return 0;
  }

  else if (grid[r][c] != ABNORMAL)
  {
    return 0;
  }

  else
  {
    int original_row = r;
    int original_column = c;

    while(r >= 0 && row < ROWS && c >= 0 && c < COLS && grid[r][c] == ABNORMAL)
    {
      grid[r][c] = TEMPORARY;
      temp = temp + 1;
      r = r - 1;
      c = c - 1;
    }
    r = original_r;
    c = original_c;

    while(r >= 0 && r < ROWS && c >= 0 && c < COLS && grid[r][c] == ABNORMAL)
    {
      grid[r][c] = TEMPORARY;
      temp = temp + 1;
      r = r - 1;
    }
    r = original_r;
    c = original_c;

    while(r >= 0 && r < ROWS && c >= 0 && c < COLS && grid[r][c] == ABNORMAL)
    {
      grid[r][c] = TEMPORARY;
      temp = temp + 1;
      r = r - 1;
      c = c + 1;
     }
    r = original_r;
    c = original_c;

    while(r >= 0 && r < ROWS && c >= 0 && c < COLS && grid[r][c] == ABNORMAL)
    {
      grid[r][c] = TEMPORARY;
      temp = temp + 1;
      c = c + 1;
    }
    r = original_r;
    c = original_c;

    while(r >= 0 && r < ROWS && c >= 0 && c < COLS && grid[r][c] == ABNORMAL)
    {
      grid[r][c] = TEMPORARY;
      temp = temp + 1;
      r = r + 1;
      c = c + 1;
    }
    r = original_r;
    c = original_c;

    while(r >= 0 && r < ROWS && c >= 0 && c < COLS && grid[r][c] == ABNORMAL)
    {
      grid[r][c] = TEMPORARY;
      temp = temp + 1;
      r = r + 1;
    }
    r = original_r;
    c = original_c;

    while(r >= 0 && r < ROWS && c >= 0 && c < COLS && grid[r][c] == ABNORMAL)
    {
      grid[r][c] = TEMPORARY;
      temp = temp + 1;
      r = r + 1;
      c = c - 1;
    }
    r = original_r;
    c = original_c;

    while(r >= 0 && r < ROWS && c >= 0 && c < COLS && grid[r][c] == ABNORMAL)
    {
      grid[r][c] = TEMPORARY;
      temp = temp + 1;
      c = c - 1;
    }
    r = original_r;
    c = original_c;

    return temp;
  }
}

Upvotes: 0

Views: 1332

Answers (3)

pm100
pm100

Reputation: 

int count = 0;
for (int i = 0; i < rows; i++)
{
    for (int j = 0; j < COLS; j++) 
    {
        if (grid[i,j] != ABNORMAL) count++;
    }
}

Upvotes: 0

Jeffrey Hantin
Jeffrey Hantin

Reputation: 36504

This appears to be a classic flood fill algorithm. A non-recursive flood fill routine is a bit tricky to write; you will need temporary storage somewhere, and the stack is the easiest place to get it. The linked article discusses some other techniques, including using the array itself as temporary space (the right-hand fill algorithm).

Upvotes: 1

Jesse Rusak
Jesse Rusak

Reputation: 57168

The easiest way to do this non-recursively is to maintain a list of places to check. Pseudocode would look like this:

list horizon = new empty list;
horizon.push(r, c);
count = 0;
while(!horizon.empty())
{
   r, c = horizon.pop();
   if(boundscheck(r, c) && grid[r][c] == ABNORMAL)
   {
        count++;
        horizon.push(r-1, c-1);
        horizon.push(r-1, c  );
        // etc ...
        grid[r][c] = TEMPORARY;
   }
}

EDIT: You should definitely look at this post on flood fill algorithms.

Upvotes: 1

Related Questions