java - 如何将2D数组拆分为不同尺寸的填字游戏？

我正在试验一个纵横填字游戏的生成器，但当它被分成不同的部分时，我就卡住了。我有一个二维数组，其中存储纵横填字游戏，如下所示：

int SIZE = 10; //This can be higher for bigger crosswords
Character[][] crossword = new Character[SIZE][SIZE];

然后我向这个纵横填字游戏中添加几个单词，例如，最后得到以下数组（。=空正方形）：

..........
..........
..C...H...
..A...O...
..TIGER...
......S...
...DOVE...
..........
..........
..........

我该如何分割这个二维数组，以便最终得到至少包含两个字母而不是一个完整单词的片段。字母也必须水平或垂直相邻，但不能对角。例如，我可以得到以下几点：

C    TIG    H    ER    DOV
A           O     S
                  E

以下内容无效，因为字母不是水平或垂直相邻的。

  O
GE
  S

我的第一个尝试是通过做以下事情来分开这件事：

int chunksize = 2; //This should vary depending on how big the pieces should be
List<Character[][]> subArrays = new ArrayList<>();
for(int i = 0; i < SIZE; i += chunksize){
    for(int j = 0; j < SIZE; j += chunksize){
        Character[][] sub = new Character[chunksize][chunksize];
        sub[0][0] = crossword[i][j];
        sub[0][1] = crossword[i][j + 1];
        sub[1][0] = crossword[i + 1][j];
        sub[1][1] = crossword[i + 1][j + 1];
        if(sub[0][0] != null || sub[0][1] != null || sub[1][0] != null || sub[1][1] != null){
            subArrays.add(sub);
        }
    }
}

但是，这可能会创建只包含一个字母的片段，或者字母不相邻的片段。我不知道该如何解决这个问题，这就是我来这里寻求帮助的原因。

最佳答案

多米诺牌包装
下面的方法创建尽可能多的size-2块。之后，任何剩余的单个字母都需要以某种方式附加到相邻的块上——例如，随机选取其中一个相邻的块。
创建一个图，其中每个位置的顶点由一个字母占据，并且在任意一对垂直或水平相邻的字母位置之间有一条边。现在计算这个图上的amaximum matching：这选择了一个最大尺寸的边子集，这样就没有顶点在多条边上发生关联。这些边对应于大小为2的块。
如果你把网格想象成一个棋盘，你会注意到每一个正方形要么是白色的要么是黑色的，没有边连接两个白色的单元格或两个黑色的单元格：这意味着图形是二分的，这反过来意味着你可以使用o（e*sqrt（v））-timeHopcroft-Karp algorithm，它比一般图的edmonds算法更快更简单。

关于java - 如何将2D数组拆分为不同尺寸的填字游戏？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/40483698/