洪水填充递归算法

本文介绍了洪水填充递归算法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在尝试创建一种可以填充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)); }