Java 二维数组，查找包含的元素

Question

我有一个这样声明的二维数组：

private Dots[][] dots = new Dots[8][8];

我正在制作一个用于教育目的的游戏，其中二维数组充满了点，每个点的颜色从四种颜色中随机 selected。游戏的目标是连接点。当您连接相同颜色的点时，它们会被删除，您会为它们加分。目前一切正常，但我想添加一个新功能：

当您关闭路径时，该路径中包含的所有点也将被删除。（见图）：

我正在考虑一种算法来找到该路径中包含的所有点，但我想不出一个。

路径存储在 LinkedList 中（可能无关紧要，但我只是说它是为了确定:)）

总结一下我的问题：我正在尝试提出一种算法来 select 蓝点之间的灰点。

注：

点可以对角连接
路径可以任意长
闭合路径可以是任何形状

编辑 1：这是游戏的样子：

编辑 2：这就是我的意思：

When you close the path, all dots contained in that path will be deleted aswell.

Answer 1

固溶体：

正确的解决方案是实施 4-connected/4-Neighbour 版本的 FloodFill 算法。

非常好看explained in the Wikipedia article。 java 中的示例可以是 found here.

天真的解决方案：

逐行，将所有字段最初着色为白色，然后将用户select编辑的字段着色为蓝色并逐行迭代，将中间的字段着色（状态：boolean select = true）灰色:

enum COLOR { BLUE, GREY, WHITE}; 

boolean select = false;

// iterate row by row
for(int x = 0; x < 8; x++) {
       for(int y = 0; y <8; y++) {
           //select mode...
           if(dots[x][y].color == COLOR.BLUE  && !change) {
                select = true;
           }
           //if we are in select and the current field is white -> make GREY
           if(select && dots[x][y].color == COLOR.WHITE) {
                dots[x][y].color = COLOR.GREY;
           }
           // if we hit another blue and are in select -> select = false
           if(select && dots[x][y].color == COLOR.BLUE) {
                select = false;
           }
    }
}

请注意，仍有一些案例需要处理：

例如如果当前迭代行是垂直的蓝色墙并且长度是 odd 它会错误地变成 select mode

Answer 2

动态规划方法 (n^2)

对于任何符合计数条件的单元格，您需要 (i,j-1),(i-1,j) 和 (i,j+1),(i+1,j)。
注意：这个单元格可能不完全在那里，它也可能在线下。

创建布尔二维数组。
让我们以下面的 6 x 6 样本为例。
/*
T T T - - -
T - T - - -
T T T - - -
- T - - - -
- T - - - -
*/
其中 T 标记闭合路径。

2 次迭代：
第一名

首先遍历矩阵，如果您发现 (i,j-1) 和 (i-1,j) 为真，则将该点包含在集合（或任何集合）中。对于边界条件，不要将它们包含在 Set 中，因为它们永远不会在封闭路径内，因此在第一次迭代结束时，您将拥有

/*
T T T F F F
T 1 T F F F
T T T F F F
F T 1 F F F
F T 1 F F F
*/
其中 1 表示包含在集合中的点。
（在这里你可能想使用 char 2d 矩阵而不是布尔值。但是如果你使用布尔值那么它也可以工作只需要执行 set.contains(new Point(i,j)))

第二

做同样的事情，但从 (n-1,n-1) 开始，这次您检查 (i+1,j),(i,j+1) 点是否为真。对于二维矩阵中的任何点，如果您发现它应该是 'F' 但它是“1”，则从集合中删除该点。

/*
T T T F F F
T 1 T F F F
T T T F F F
F T F F F F
F T F F F F
*/

这样经过2次n^2次操作。您将拥有包含所需积分的套装。

是的，1 也将作为后续迭代的 T。
简而言之，与此处的 DP 不同，我们从 TOP-LEFT 遍历到 BOTTOM-RIGHT，从 BOTTOM-RIGHT 遍历到 TOP-LEFT，以便准确找出闭合路径内的点。
F - 不合格
T - 仅符合计数条件
1 - 与 T 相同，但也被添加到输出集中

Java 二维数组，查找包含的元素

Java 2D Array, find containing elements

java

arrays

algorithm

math

2d