洪水填充递归算法 [英] Flood fill recursive algorithm
问题描述
我正在尝试创建一种可以填充c#中的int数组的算法。基本上,作为MS Paint中的填充工具,我有一种颜色,如果我在数组中选择(x,y)坐标,它会将具有相同初始颜色的所有邻居替换为新颜色。
I'm trying to make an algorithm that could fill an int array in c#. Basically, as the fill tool in MS Paint, I have a color and if I choose (x,y) coordinates in the array, it replaces all the neighbours with the same initial color with the new color.
例如:
[0,0,0]
[0,1,0]
[1,1,0]
如果我将3放在(0,0)中,数组变为:
If I put 3 in (0,0), the array becomes :
[3,3,3]
[3,1,3]
[1,1,3]
所以我尝试了递归并且确实有效,但并非一直如此。实际上,有时我会出现堆栈溢出错误(似乎合适)。
这是我的代码,如果您能告诉我哪里出了问题,那将是很好的:)
So I tried it in recursive and it does work, but not all the time. Actually, I have sometimes a "Stack Overflow" error (seems appropriate). Here's my code, it would be great if you could tell me what's wrong :)
public int[,] fill(int[,] array, int x, int y, int initialInt, int newInt)
{
if (array[x, y] == initialInt)
{
array[x, y] = newInt;
if (x < array.GetLength(0) - 1)
array = fill(array, (x + 1), y, initialInt, newInt);
if (x > 0)
array = fill(array, (x - 1), y, initialInt, newInt);
if (y < array.GetLength(1) - 1)
array = fill(array, x, (y + 1), initialInt, newInt);
if (y > 0)
array = fill(array, x, (y - 1), initialInt, newInt);
}
return array;
}
谢谢!
推荐答案
如何使用堆栈/队列来管理剩余的工作?
How about using a stack/queue to manage the remaining work?
public void Fill(int[,] array, int x, int y, int newInt)
{
int initial = array[x,y];
Queue<Tuple<int,int>> queue = new Queue<Tuple<int,int>>();
queue.Push(new Tuple<int, int>(x, y));
while (queue.Any())
{
Tuple<int, int> 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<Tuple<int, int>> 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<int, int>(x, y));
}
这篇关于洪水填充递归算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!