Blob ... как писать не рекурсивно - PullRequest
Новая
       19

Blob ... как писать не рекурсивно

0 голосов
/ 24 марта 2009

Я написал следующую программу, используя рекурсию, но я не могу понять, как написать ее не рекурсивно. Каждый раз, когда я запускаю свою нерекурсивную версию, цифры меняются. Любые предложения о том, как написать следующий метод без рекурсии? 

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

Ответы [ 3 ]

1 голос
/ 24 марта 2009

Самый простой способ сделать это нерекурсивно - это вести список мест для проверки. Псевдокод будет выглядеть так: 

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

РЕДАКТИРОВАТЬ: Вы должны обязательно посмотреть этот пост на алгоритмы заливки .

1 голос
/ 24 марта 2009

Похоже, это классический алгоритм заливки . Нерекурсивную процедуру заполнения потока немного сложно написать; где-то вам понадобится временное хранилище, а стек - самое простое место для его получения. В связанной статье обсуждаются некоторые другие методы, в том числе использование самого массива в качестве временного пространства (алгоритм правой заливки).

0 голосов
/ 24 марта 2009 
int count = 0;
for (int i = 0; i < rows; i++)
{
    for (int j = 0; j < COLS; j++) 
    {
        if (grid[i,j] != ABNORMAL) count++;
    }
}
...