Erreur de segmentation d'inondation récursive

Question

J'essaie d'implanter un remplissage. Cela fonctionne très bien sur une matrice 500x500:

int ud[]={1,0,-1,0}; 
int lr[]={0,1,0,-1}; 

void fl(int x,int y) 
{ 
    if(x<=0||x>n||y<=0||y>m) 
    return; 
    if(mat[x][y]) // seg fault occurs for this condition 
    return; 
    mat[x][y]=1; 
    for(int i=0;i<4;i++) 
    fl(x+ud[i],y+lr[i]); 
} 

Mais sur une matrice 600 X 600 cela donne un défaut de segmentation. Qu'est-ce qui pourrait causer ça?

Answer 1

Si N et M sont la taille de la grille, vous devez avoir un opérateur de comparaison> =. Comme si:

int ud[]={1,0,-1,0}; 
int lr[]={0,1,0,-1}; 

void fl(int x,int y) 
{ 
    if(x<=0||x>=n||y<=0||y>=m||mat[x][y]) 
    return; 
    mat[x][y]=1; 
    for(int i=0;i<4;i++) 
    fl(x+ud[i],y+lr[i]); 
} 

Answer 2

Si vous ajoutez une calque dans votre code:

#include <stdio.h> 
#include <iostream> 

using namespace std; 


int mat[1000][1000]; 
int n,m; 
int ud[]={1,0,-1,0}; 
int lr[]={0,1,0,-1}; 

void fl(int x,int y, int depth) 
{ 
    if(x<=0||x>n||y<=0||y>m||mat[x][y]) { 
    return; 
    } 

    std::cout << x << ", " << y << " (" << depth << ")\n"; 

    mat[x][y]=1; 

    for(int i=0;i<4;i++) { 
    fl(x+ud[i],y+lr[i],depth+1); 
    } 
} 

int main(int argc, char const *argv[]) 
{ 

    n=9,m=9; 
    fl(1,1,0); 

    return 0; 
} 

Et observez le comportement:

1, 1 (0) 
2, 1 (1) 
3, 1 (2) 
4, 1 (3) 
5, 1 (4) 
6, 1 (5) 
7, 1 (6) 
8, 1 (7) 
9, 1 (8) 
9, 2 (9) 
9, 3 (10) 
9, 4 (11) 
9, 5 (12) 
9, 6 (13) 
9, 7 (14) 
9, 8 (15) 
9, 9 (16) 
8, 9 (17) 
7, 9 (18) 
6, 9 (19) 
5, 9 (20) 
4, 9 (21) 
3, 9 (22) 
2, 9 (23) 
1, 9 (24) 
1, 8 (25) 
2, 8 (26) 
3, 8 (27) 
4, 8 (28) 
5, 8 (29) 
6, 8 (30) 
7, 8 (31) 
8, 8 (32) 
8, 7 (33) 
7, 7 (34) 
6, 7 (35) 
5, 7 (36) 
4, 7 (37) 
3, 7 (38) 
2, 7 (39) 
1, 7 (40) 
1, 6 (41) 
2, 6 (42) 
3, 6 (43) 
4, 6 (44) 
5, 6 (45) 
6, 6 (46) 
7, 6 (47) 
8, 6 (48) 
8, 5 (49) 
7, 5 (50) 
6, 5 (51) 
5, 5 (52) 
4, 5 (53) 
3, 5 (54) 
2, 5 (55) 
1, 5 (56) 
1, 4 (57) 
2, 4 (58) 
3, 4 (59) 
4, 4 (60) 
5, 4 (61) 
6, 4 (62) 
7, 4 (63) 
8, 4 (64) 
8, 3 (65) 
7, 3 (66) 
6, 3 (67) 
5, 3 (68) 
4, 3 (69) 
3, 3 (70) 
2, 3 (71) 
1, 3 (72) 
1, 2 (73) 
2, 2 (74) 
3, 2 (75) 
4, 2 (76) 
5, 2 (77) 
6, 2 (78) 
7, 2 (79) 
8, 2 (80) 

Vous remarquerez qu'il suit un schéma comme un serpent, tout en continuant de plus en plus profonde et plus profonde dans la récursivité.

C'était avec grille 9x9, imaginez la profondeur, il va de pair avec 600x600. Qu'est-ce qui se passe, c'est que vous débordez de la pile, et votre programme se bloque.