我正在尝试创建一种填充方法,该方法采用用户指定的初始坐标,检查字符,然后根据需要进行更改。这样做之后,它会检查相邻的方 block 并重复该过程。经过一些研究,我遇到了 flood fill algorithm 并在尝试之后(它有效但不能满足我对 250 x 250 个字符的数组的最大要求)。
我原来的洪水填充算法如下:
public static void fillArea (int x, int y, char original, char fill){
if (picture[y-1][x-1] != original){
return;
}
picture[y-1][x-1] = fill;
fillArea (x-1, y, original, fill);
fillArea (x+1, y, original, fill);
fillArea (x, y-1, original, fill);
fillArea (x, y+1, original, fill);
return;
}
测试后,我开始尝试队列方法,如Wikipedia 中所解释的那样和 this question asked previously关于类似的问题。到目前为止,我想出了以下代码:
public static void fillArea (int x, int y, char original, char fill){
if (x != 0)
x--;
if (y!= 0)
y--;
Queue<Point> queue = new LinkedList<Point>();
if (picture[y][x] != original){
return;
}
queue.add(new Point(x, y));
while (!queue.isEmpty()){
Point p = queue.remove();
if (picture[p.y][p.x] == original){
picture[p.y][p.x] = fill;
queue.add(new Point(p.x-1, p.y));
queue.add(new Point(p.x+1, p.y));
queue.add(new Point(p.x, p.y-1));
queue.add(new Point(p.x, p.y+1));
}
}
return;
}
虽然第一种递归方法能够处理较小的值,但当数组变得太大时它就不起作用了。但是,第二种方法将我带入某种无限循环,由于我对队列缺乏经验,我无法识别这种循环。我如何优化第一个代码示例以处理更大的样本或修复第二个代码示例以提供结果?任何人都可以解释如何对这两个中的任何一个进行编码或者我做错了什么吗?
谢谢!
编辑:我能够在第二个代码中找到无限循环错误(已修复)但是基于队列的方法没有填充完整区域。事实上,它比基于递归的方法填充更少的区域。 编辑 2:它现在适用于方阵。我怎样才能确保它也适用于矩形阵列(第二种方法)。
最佳答案
不应该
if (picture[p.y][p.x] == original){
picture[p.y-1][p.x-1] = fill;
成为
if (picture[p.y][p.x] == original){
picture[p.y][p.x] = fill;
在队列中 - 方法?
关于java - 洪水填充优化 : Attempting to Using a Queue,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12552098/