Blob ...非再帰的に書く方法

Question

私は以下のプログラムを再帰を使って書いていますが、再帰的に書く方法を見つけることはできません。私が非再帰的なバージョンを走らせるたびに、その数字は消えてしまいます。どのように再帰せずに次のメソッドを記述するための任意の提案？

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

Answer 1

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

Answer 2

を非再帰的にこれを行う最も簡単な方法は、チェックする場所のリストを維持することです。擬似コードは次のようになります。

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：あなたは間違いなくflood fill algorithmsに、この記事をご覧ください。

Answer 3

これは古典的なflood fillアルゴリズムのようです。非再帰的なflood fillルーチンは少し書くのが難しいです。あなたはどこかに一時的なストレージが必要で、スタックはそれを取得する最も簡単な場所です。リンクされた記事では、配列自体を一時的なスペース（右の塗りつぶしアルゴリズム）として使用する方法など、いくつかの他の手法について説明します。