洪水填充递归算法
我正在尝试制作一个可以在c＃中填充int数组的算法。 基本上，作为MS Paint中的填充工具，我有一个颜色，如果我在数组中选择（x，y）坐标，它会用新颜色替换所有具有相同初始颜色的邻居。
例如：
[0,0,0] [0,1,0] [1,1,0] 如果我将3放入（0,0），则数组变为：
[3,3,3] [3,1,3] [1,1,3]
所以我在递归中尝试了它并且确实有效，但并非总是如此。 实际上，我有时会出现“Stack Overflow”错误（似乎合适）。 这是我的代码，如果你能告诉我什么是错的话会很棒:)
public int[,] fill(int[,] array, int x, int y, int initialInt, int newInt) { if (array[x, y] == initialInt) { array[x, y] = newInt; if (x 0) array = fill(array, (x - 1), y, initialInt, newInt); if (y 0) array = fill(array, x, (y - 1), initialInt, newInt); } return array; }
谢谢 ！
如何使用堆栈/队列来管理剩余的工作？
public void Fill(int[,] array, int x, int y, int newInt) { int initial = array[x,y]; Queue> queue = new Queue>(); queue.Push(new Tuple(x, y)); while (queue.Any()) { Tuple point = queue.Dequeue(); if (array[point.Value1, point.Value2] != initial) continue; array[point.Value1, point.Value2] = newInt; EnqueueIfMatches(array, queue, point.Value1 - 1, point.Value2, initial); EnqueueIfMatches(array, queue, point.Value1 + 1, point.Value2, initial); EnqueueIfMatches(array, queue, point.Value1, point.Value2 - 1, initial); EnqueueIfMatches(array, queue, point.Value1, point.Value2 + 1, initial); } } private void EnqueueIfMatches(int[,] array, Queue> queue, int x, int y, int initial) { if (x < 0 || x >= array.GetLength(0) || y < 0 || y >= array.GetLength(1)) return; if (array[x, y] == initial) queue.Enqueue(new Tuple(x, y)); }
这是一个教科书示例，说明为什么使用递归并不总是合适的。 递归对于遍历本质上递归的数据结构（例如树）非常有用，但是像素数据的数组却不是。
我建议在代码中添加一个计数器来打印fill()函数的调用频率。 在每次函数调用时，您的机器必须在内存中的堆栈上创建一个新帧（因此它知道在函数结束后它必须返回的内存位置）。 递归图像填充算法调用fill()函数很多次，因此堆栈将非常快速地增长。 它的尺寸有限，因此它会溢出以获得更大的图片。
解决方案是实现迭代填充算法，使用循环而不是递归来迭代像素。
有关递归和堆栈溢出的维基百科，或Foley等人的“计算机图形学，原理和实践”。 有关基本计算机图形算法的更详细介绍。
正如已经提出的那样，问题在于递归调用的数量。 在32位机器上你有4个字节的指针，所以如果你有一个512 * 512的图像并且你想要填充整个东西，单独的函数指针将在你的堆栈上占用512 * 512 * 4bytes = 1MB的内存。 这是堆栈的默认大小 。 无论函数指针如何，你都会传递另外5个引用（ array ， x ， y ， initialInt ， newInt ），它们都被复制，每次调用都作为临时对象，并且在函数调用终止之前都在堆栈中。 在相同大小的图像上，这些是另一个512 * 512 * 5 * 4bytes = 5MB的内存。
要解决您的问题，您可以修改 （与上面相同的链接）堆栈的大小。
另外，为了节省一些堆栈空间，您可以考虑将参数包装在单个对象中，在这种情况下，每次调用只有4位临时内存，而不是20位。
尽管如此，正如指出的那样，最好的解决方案是迭代地重写算法。