Flood Fill 优化:尝试使用队列 [英] Flood Fill Optimization: Attempting to Using a Queue

问题描述

我正在尝试创建一种填充方法，该方法采用用户指定的初始坐标，检查字符，然后根据需要进行更改.这样做之后，它然后检查相邻的方块并重复该过程.经过一些研究，我遇到了洪水填充算法并尝试了它(它可以工作，但不能满足我对 250 x 250 个字符的数组的最大要求).

I am trying to create a filling method which takes the initial coordinate specified by the user, checks the character and then changes it as desired. After doing so, it then checks adjacent squares and repeats the process. After some research, I came across the flood fill algorithm and after trying that (it works but cannot meet my maximum requirement of an array of 250 by 250 characters).

我原来的洪水填充算法如下:

My original flood fill algorithm was as follows:

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;
}

经过测试后，我开始尝试使用 维基百科 上所述的队列方法和之前就类似问题提出过这个问题.到目前为止，我已经想出了以下代码:

After testing, I began to try the Queue method as explained on Wikipedia and this question asked previously regarding a similar issue. So far, I have come up with the following code:

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;
}

虽然第一个递归方法能够处理较小的值，但当数组变得太大时它不起作用.但是，第二种方法将我带入某种无限循环中，由于我对队列缺乏经验，我无法识别这种循环.我如何优化第一个代码示例以处理更大的样本，或者修复第二个代码示例以便给出结果?谁能解释一下如何编写这两个代码中的任何一个或我做错了什么?

While the first, recursive method was able to work for smaller values, it does not work when the array gets too large. However, the second method is taking me into some sort of infinite loop that I am unable to identify due to my inexperience with Queues. How can I either optimize the first code sample to work with larger samples or fix the second so that it gives results? Can anyone explain how to code any of these two or what I am doing wrong?

谢谢！

我能够在第二个代码中找到无限循环错误(已修复)，但基于队列的方法没有填满整个区域.事实上，它比基于递归的方法填充的区域更少.编辑 2:它现在适用于方形阵列.我如何确保它也适用于矩形数组(第二种方法).

I was able to find the infinite loop error in the second code (it has been fixed) but the queue based method does not fill the complete area. In fact, it fills less of an area than the recursion-based method. EDIT 2: It now works for square arrays. How can I ensure that it works for rectangular arrays as well (the second method).

推荐答案

不应该

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;

在队列中 - 方法?

这篇关于Flood Fill 优化:尝试使用队列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！