5

我正在尝试创建一个填充方法，该方法采用用户指定的初始坐标，检查字符，然后根据需要更改它。这样做之后，它会检查相邻的方格并重复该过程。经过一番研究，我遇到了洪水填充算法，并在尝试之后（它可以工作，但不能满足我对 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;
}

测试后，我开始尝试 Queue 方法，如Wikipedia上解释的那样，这个问题之前就类似的问题提出过。到目前为止，我已经想出了以下代码：

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：它现在适用于方形数组。如何确保它也适用于矩形阵列（第二种方法）。

4

2 回答 2

1

不应该

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;

在队列中 - 方法？

于 2012-09-23T12:36:52.287 回答
1

作为参考，该问题已通过在它正在处理的数组周围添加一个缓冲区边框来解决。例如，如果要填充的数组是

000
000
000

它被制成

   #####
   #000#
   #000#
   #000#
   #####

在被处理之前。

于 2012-09-23T12:42:27.200 回答