Blob ... comment écrire de manière non récursive

Question

J'ai écrit le programme suivant, en utilisant la récursivité, mais je n'arrive pas à comprendre comment l'écrire de façon non récursive. Chaque fois que je lance ma version non récursive, les chiffres sont loin. Des suggestions sur la façon d'écrire la méthode suivante sans récursion?

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

C'est ce que j'ai essayé 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; 
    } 
} 

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

La meilleure façon de le faire non-récursive est de maintenir une liste des endroits à vérifier. Pseudocode ressemblerait à ceci:

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: Vous devriez vraiment regarder à ce poste sur flood fill algorithms.

Answer 3

Cela semble être un algorithme classique flood fill. Une routine de remplissage d'inondation non récursif est un peu difficile à écrire; vous aurez besoin d'un stockage temporaire quelque part, et la pile est l'endroit le plus facile pour l'obtenir. L'article lié traite d'autres techniques, notamment l'utilisation du tableau lui-même en tant qu'espace temporaire (l'algorithme de remplissage à droite).