0

我已经使用递归编写了以下程序，但我不知道如何以非递归方式编写它。每次我运行我的非递归版本时，数字都会偏离。关于如何在没有递归的情况下编写以下方法的任何建议？

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

这是我尝试过的顺便说一句：

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

3 回答 3

1

以非递归方式执行此操作的最简单方法是维护要检查的位置列表。伪代码如下所示：

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

编辑：你绝对应该看看这篇关于洪水填充算法的帖子。

于 2009-03-23T23:16:27.083 回答
1

这似乎是一个经典的洪水填充算法。一个非递归的洪水填充例程写起来有点棘手；您将需要在某个地方进行临时存储，而堆栈是最容易获得它的地方。链接的文章讨论了其他一些技术，包括将数组本身用作临时空间（右手填充算法）。

于 2009-03-23T23:17:59.997 回答
0 
int count = 0;
for (int i = 0; i < rows; i++)
{
    for (int j = 0; j < COLS; j++) 
    {
        if (grid[i,j] != ABNORMAL) count++;
    }
}
于 2009-03-23T23:01:14.750 回答