java - 处理二维文本(Ruzzle 解算器)

Question

我正在尝试编写一个 Ruzzle 求解器 Java 应用程序以用于学习目的。我在 Ruzzle 类型的 map 中“查找单词”方面遇到了一些问题。

Ruzzle map 示例(由 4 行 4 列组成，每个单元格有 1 个字母):

Z O O H
E Y L H
I E L I
H O F M

http://www.maclife.com/files/imagecache/futureus_imagegallery_fullsize/gallery/ruzzle1.jpg

我想获得您可以在此类 map 中找到的所有可能单词的列表。

难度:你可以通过垂直、水平和对角附加字母来找到一个单词(例如:“HELLO”)。

到目前为止，我创建了 3 个类:

• Ruzzlesolver.java

• Letter.java

• Map.java

字母类

描述 map 的单个字母，其字段是 X 和 Y 位置以及单元格的字符。

Ruzzlesolver 类

这是主类。

• 它读取Ruzzle map (控制台中的逐行输入)
• 它读取dictionnary.txt文件
• 它将 map 与字典文件进行比较
• 它写入results.txt文件

每一行都存储在一个字符数组中。然后我从获得的 4 个数组中创建一个新的 Map 对象。

map 类

这是 Map 对象的构造函数:

public Map(final char[] pTab1, final char[] pTab2, final char[] pTab3, final char[] pTab4)
{
    this.aLettres = new ArrayList<Letter>();
    for (int i = 0 ; i < 4 ; i++) {
        this.aLettres.add(new Letter(1, i+1, pTab1[i]));}
    for (int i = 0 ; i < 4 ; i++) {
        this.aLettres.add(new Letter(2, i+1, pTab2[i]));}
    for (int i = 0 ; i < 4 ; i++) {
        this.aLettres.add(new Letter(3, i+1, pTab3[i]));}
    for (int i = 0 ; i < 4 ; i++) {
        this.aLettres.add(new Letter(4, i+1, pTab4[i]));}
}

this.aLettres 是包含 map 16 个字母的 ArrayList。

每个字母都知道它的列(X 位置:“i+1”)、行(Y 位置:“1、2、3 和 4”)及其字符(“pTab[i]”)。

现在我们知道了 map 和每个字母的位置，我们可以开始查找单词了。

contains() 方法

这是我的问题:我被困在使用以下方法:

如何称呼

1. 我从 Ruzzlesolver 类的词典中选择一个单词。

2. 我在 Map 对象上调用 contains() 方法，并使用此单词作为参数:

   if (this.aMap.contains(vMot)) {/*print vMot in the result.txt file*/}
   

contains() 方法如何工作

1. 变量:

       char[] vChars = new char[pMot.length()];
       ArrayList<Letter> vFoundCharS1 = new ArrayList<Letter>();
   

2. 将 pMot 的每个字符存储在 ArrayList 中:

       for (int i = 0 ; i < pMot.length() ; i++) {
           vChars[i] = pMot.charAt(i);
       }
   

3. 搜索 pMot 的第一个字符:

       for (Letter vL : this.aLettres) {
           if (vL.getChar() == vChars[0]) {
               vFoundCharS1.add(vL);
               return true;
           }
       }
   

4. 我被困住了。

如果我继续这种方法，随着我的进步，我将不得不创建越来越长的 block 。此外，我需要编写 16 个 block 来考虑每种长度的可能性。

我确信这是一个错误的方法。您将如何实现这样的治疗？

预先非常感谢您的帮助。

PS:对于语法/英语错误，我深表歉意，英语不是我的母语。

Answer 1

如果我正确理解了这个问题，你可以为下一个字母选择每个相邻的单元格，对吧？在这种情况下，下面的代码(我认为)可以解决您的问题。

我更改了 Map 的构造函数，因为使用 char 的二维数组更容易。

函数 contains 的作用正是您的步骤 3 所描述的:找到第一个字母并尝试从那里开始搜索。函数 findRecursively 递归地搜索单词的其余部分。

public class Map {
    private char[][] board;

    public Map(final char[] pTab1, final char[] pTab2, 
           final char[] pTab3, final char[] pTab4) {
        board = new char[4][4];

        for (int i = 0 ; i < 4 ; i++) {
            board[0][i] = pTab1(i);
            board[1][i] = pTab2(i);
            board[2][i] = pTab3(i);
            board[3][i] = pTab4(i);
        }
    }

    public boolean contains(String word) {
        char[] array = word.toCharArray();

        // empty string is trivial
        if (array.length == 0)
            return true;

        for(int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                if (board[i][j] == array[0] && findRecursively(i, j, array, 1))
                    return true;
            }
        }

        return false;
    }

    public boolean isValid(int i, int j) {
        return (0 <= i && i < 4) && (0 <= j && j < 4);
    }

    public boolean findRecursively(int i, int j, char[] array, int index) {
        // reached end of word
        if (index == array.length) {
            return true;
        } else {
            // loop over all neighbors
            for (int di = -1; di <= 1; di++) {
                for (int dj = -1; dj <= 1; dj++) {
                    // skip cell itself and invalid cells
                    if (!(di == 0 && dj == 0) && isValid(i+di, j+dj)) {
                        if (board[i+di][j+dj] == array[index] 
                              && findRecursively(i+di, j+dj, array, index+1))
                            return true;
                    }
                }
            }

            return false;
        }           
    }
}