1

我正在尝试为学习目的编写一个 Ruzzle 求解器 Java 应用程序。在 Ruzzle 类型的地图中“找词”的问题我有一个小问题。

Ruzzle 地图示例（由 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

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

难度：您可以通过垂直、水平和对角附加字母来找到一个单词（例如：“HELLO”）。

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

  • Ruzzlesolver.java

  • 字母.java

  • 地图.java

字母类

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

Ruzzlesolver 类

这是主要课程。

  • 它读取Ruzzle 地图（在控制台中逐行输入）
  • 它读取dictionnary.txt文件
  • 它将地图与字典文件进行比较
  • 它写入results.txt文件

每行都存储在一个 char 数组中。然后我从 4 个获得的数组中创建一个新的 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 是包含地图的 16 个字母中的每一个的 ArrayList。

每个字母都知道它的列（X 位置：“i+1”）、它的行（Y 位置：“1、2、3 和 4”）和它的字符（“pTab[i]”）。

既然我们知道了每个字母的地图和位置，我们就可以开始找单词了。

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. 我被困住了。


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

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

非常感谢您的帮助。

PS：我为语法/英语错误道歉，英语不是我的母语。

4

1 回答 1

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;
        }           
    }
}
于 2013-05-22T16:56:14.450 回答