1

我正在尝试用 Java 制作类似扫雷的游戏,并且我已经完成了大部分工作。我需要帮助的是 FloodFill - http://en.wikipedia.org/wiki/Flood_fill

有人可以解释它是如何工作的吗?我在网上看过,但我不太明白解释,所以我认为在这里问会更容易。

在我的扫雷中,我有:

JButton[] btn = new JButton[100]//buttons being clicked and displaying the values/bombs
int[] mines = new int[100];//int array holding the values for each button.

网格是一个 10x10 的网格,所以说你点击的按钮是 btn[14],

btn[4]  // north of btn[14](14-10)
btn[24] // south of btn[14](14+10)
btn[13] //  west of btn[14](14-1)
btn[15] //  east of btn[14](14+1)

回到这个问题,有人可以向我解释一下吗?

编辑: 我将我的代码更改为 2D,所以现在不是上面的代码

btn[1][4]//row one, column 4

单击按钮时,我希望它检查一个名为 mines[][] 的变量,该变量具有值,如果该值等于 0(在初始单击附近),它会更改 BG

btn[x][y].setBackground(Color.GRAY);
4

2 回答 2

8

它是一种递归算法。您从 2D 网格 [x,y] 中的某个起始位置开始,然后查看所有方向并尽可能填充它们。如果 (x,y) 无法填写,则返回。

void floodFill( int x, int y ) {
   if ( btn( x, y ) isFillable ) {
       fillBtn(x,y);
       floodFill( x+1, y );
       floodFill( x-1, y );
       floodFill( x, y-1 );
       floodFill( x, y+1 );
   } else {
       return;
   }
}

(省略检查网格边界)

于 2012-12-28T21:39:19.597 回答
2

我想你主要是在问洪水填充。实际上它是一种简单而通用的递归算法。它可以解决您的数据结构是 1D 还是 2D 的任何问题。对于 2D 版本,@RMoeller 给出了答案。对于您之前的一维声明,它也类似于这样:

void floodFill( int pos ) {
   if ( btn( pos ) isFillable ) {
       fillBtn(pos);
       floodFill( pos+1 );
       floodFill( pos-1 );
       floodFill( pos+10 );
       floodFill( pos-10 );
   } else {
       return;
   }
}

您应该记住的一件事是,floodfill 和几乎所有递归算法都需要检查边界。否则你可能会陷入无限循环或得到错误的结果。在上面的例子中(一维版本),你应该检查是否: pos >= 1 && pos <= 100 类似于要检查的二维版本:​​ x >= 1 && x <= 10 && y>=1 && y <=10

希望这可以帮助。

于 2012-12-29T01:34:38.910 回答