1

所以递归不是我的强项，我一直面临挑战，要创建一个递归的 floodFill 函数，如果值为零，则用 1 填充整数向量的向量。由于我以外的原因，我的代码不断出现段错误。也许我的代码会让这听起来更清楚。

这是要填充的网格：

vector<vector<int> > grid_;

它属于我创建的一个名为“Grid”的对象，它基本上是一组帮助操作向量的函数。网格的值被初始化为全零。

这是我的洪水填充功能：

void floodFill(int x, int y, Grid & G)
{

if (G.getValue(x,y))
{
    G.setValue(x,y,1);
    if(x < G.getColumns()-1 && x >= 0 && y < G.getRows()-1 && y >= 0)
    floodFill(x+1,y,G);

    if(x < G.getColumns()-1 && x >= 0 && y < G.getRows()-1 && y >= 0)
    floodFill(x,y+1,G);

    if(x < G.getColumns()-1 && x >= 0 && y < G.getRows()-1 && y >= 0)
    floodFill(x-1,y,G);

    if(x < G.getColumns()-1 && x >= 0 && y < G.getRows()-1 && y >= 0)
    floodFill(x,y-1,G);

}       
}

这里的目的是让函数检查一个点的值是否为零，如果是，则将其更改为 1。然后它应该检查它上面的那个。它会这样做，直到找到 1 或到达向量的末尾。然后它尝试另一个方向并继续前进，直到与上述相同的条件，依此类推，直到洪水充满。

谁能帮我解决这个问题？也许告诉我怎么了？

谢谢！

4

3 回答 3

1 
if(x < G.getColumns()-1 && x >= 0 && y < G.getRows()-1 && y >= 0)
    floodFill(x-1,y,G);

将不起作用，因为如果您可以访问基础向量的索引 -1x == 0

同样适用floodFill(x,y-1,G);

于 2012-05-17T01:16:49.490 回答
1

这段代码有很多问题。首先检查if(G.getValue(x,y))某个位置的值是否为 1，如果是，则使用 .将其设置为 1 G.setValue(x,y,1)。想一想，这不可能。您何时将非零值设置为 1？

然后，另一个更微妙的点是，如果它们已经设置为 1，则不应递归到邻居。

就目前而言，您拥有的代码可能会一直运行，直到您溢出堆栈，因为只会在连接到您从哪里开始的 1 上永远递归。

于 2012-05-17T10:01:15.290 回答
0

这个怎么样？

void floodFill(int x, int y, Grid &g) {
  if(x >= g.getColumns() || y >= g.getRows()) {
    return;
  }

  floodFill(x+1, y, g);

  if( x == 0 ) {
    floodFill(x, y+1, g);
  }

  g.setValue(x, y, 1)
}

我认为这将填充网格，而无需每次多次击中相同的坐标，并且只要任一索引超出范围，它就会返回，因此不会出现段错误。

于 2012-05-17T02:00:25.157 回答