如何将一个二维数组分割成不同大小的块以制作填字游戏？

Question

我正在尝试使用一个生成器来制作填字游戏，但是当需要将其拆分成不同的部分时，我卡住了。我有一个二维数组，用于存储像这样的填字游戏：

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

然后我为这个纵横字谜添加了一些单词，例如最终得到以下数组（.=空方块）：

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

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

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

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

- FewWords

---

你为什么想要拆分你的数组？我理解你的问题，但不太清楚你想达到什么目的。 - eldo

是的，但它不应该总是一个固定的数字。它应该适应使得这些片段遵循给定的格式。只要这个片段不包含整个单词，那么它是否有2、3或更多字母并不重要。我提供的函数只是一个例子，我感觉它可能不是解决问题的正确方法。 - FewWords

这听起来像一个有趣的单词谜题，但我认为有些人感到困惑，因为我所说的“纵横填字游戏”是不同的：你会得到一些线索（例如“和平的象征”），用于填写特定的位置（例如“横4”）。 - j_random_hacker

创建尽可能多的大小为2的块的解决方案是否可行？根据布局，它还可能创建最多大小为5的块，但通常情况下无法避免这些问题：考虑一下以“星形”排列的5个字母，中心有一个字母，每个水平和垂直相邻位置都包含一个字母：没有办法将其分成更小的部分，而不留下至少1个单字母部分。 - j_random_hacker

我的方法基本上是尽可能地创建许多大小为2的块，因此随后，任何剩余的单个字母都需要以某种方式作为第3个（或可能是第4个或第5个）字母附加到现有块上。虽然可以用各种方式实现这一点，但我想不出一种策略来排除创建大小为5的块的可能性。 - j_random_hacker

Answer 1

多米诺骨牌堆叠

以下方法尽可能创建多个大小为2的块。然后，任何剩余的单个字母都需要以某种方式附加到相邻的块上——例如，通过随机选择相邻的块之一。

创建一个图，其中每个由字母占据的位置都有一个顶点，并且在垂直或水平相邻的字母位置之间存在边缘。现在在此图上计算最大匹配：这选择了一个最大大小的边缘子集，使得没有顶点与多于一个边缘相接。这些边缘对应于大小为2的块。

如果将网格想象成棋盘，则会注意到每个方格都是白色或黑色，并且没有边缘连接两个白色单元格或两个黑色单元格：这意味着该图是二分图，从而意味着您可以使用O（|E|*sqrt（|V|））时间Hopcroft-Karp算法，它比Edmonds算法更快且更简单，适用于一般图形。

- j_random_hacker

---

我不明白其中任何一个词，但是...哇！ - Ridcully

Answer 2

我建议你做的是将每一行和每一列都转换成自己的字符串。

例如： 前三行

..........
..........
..C...H...

前三列

..........
..........
..CAT.....

你可以使用for循环来实现这个功能，例如：

for(int x = 0; x < SIZE; x++){
    //Loop through rows and columns.
    //(eg:crossword[x][y] in this loop will extract a row of values)
    //(eg:crossword[y][x] in this loop will extract a column of values)
    for(int y = 0; y < SIZE; y++){
        //Code to build each row/column string
    }
    //Add extracted Strings to an ArrayList?
}

在你拥有这些字符串后，你可以使用以下方式进行分割：（假设 . 仍然是你的分隔符）

s.split("\\.");

这将使您得到每行和列的字符串数组

从中分别提取C和H作为字符串

..........
..........
..C...H...

从中提取CAT作为一个字符串

..........
..........
..CAT.....

这应该让你能够检查它们的长度是否符合块大小并返回所需的组合。

希望我已经正确理解了问题，或者至少给你提供了一些可用于开发你正在寻找的解决方案的想法。

- Adam J