如何将一个2D数组分成不同大小的部分来玩填字游戏

Question

我正在试验一个填字游戏的生成器，但当我把它分成不同的部分时，我陷入了困境。我有一个二维数组，我像这样存储填字游戏:

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

然后我在这个填字游戏中添加一些单词，例如，以下面的数组()结束。= empty square):

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

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

Answer 1

Domino包装

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

创建一个图形，每个字母占据的位置有一个顶点，在任何一对垂直或水平相邻的字母位置之间有一条边。现在在这个图上计算一个最大匹配:选择一个最大大小的边子集，使得没有顶点发生在超过一条边上。这些边对应大小为2的块。

如果你把网格想象成一个棋盘，你会注意到每个正方形要么是白色要么是黑色，没有边连接两个白色或两个黑色单元:这意味着图是二部的，这反过来意味着你可以使用O(|E|*sqrt(|V|))时间Hopcroft-Karp算法，它比一般图的Edmonds算法更快更简单。

Answer 2

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

如:前3行

..........
..........
..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.....

这应该允许您根据块大小检查它们的长度并返回您想要的组合。

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