c++ - 递归 Floodfill 段错误

Question

我正在尝试实现 floodfill。这适用于 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]);
}

但是在 600 X 600 的矩阵上它给出了段错误。什么可能导致这种情况？

Answer 1

如果您在代码中添加一些跟踪:

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

并观察行为:

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) 

您会注意到它遵循蛇形模式，同时不断深入递归。

这是 9x9 网格，想象一下 600x600 有多深。

发生的事情是堆栈溢出，程序崩溃。