1

所以，我正在尝试编写一个模拟游戏 Boggle 的 java 程序。它输入两个文本文件，第一个是代表 nxn 板的文本文件，其中第一行包含板的尺寸，即 4x4.txt 文件的第一行将是数字 4，其余将是板本身。第二个 txt 文件将是一个包含所有可能的字典单词的文件。

我首先想验证我们用来从 nxn 网格生成所有可能的字符串输出的算法是否正确。我使用深度优先搜索算法来做到这一点。

我相信我已经把这部分弄对了。但是，现在我要实施一种启发式方法来帮助识别死胡同，并避免搜索浪费的单词和浪费时间。我不知道这应该如何进行。任何帮助，将不胜感激。

这是我到目前为止的代码。就像我说的，我的 depthFirstSearch 方法是正确的，并且给了我正确的输出。我也不喜欢使用 TreeSet 来存储字典单词，因为我什至不确定这是否正确。我这样做是因为我知道它是存储可能的字符串组合的正确 ADT。

import java.io.*;
import java.util.*;

public class Boggle {

    //Above main declare a static long int numWordsFormed=0;
    private static int numWordsFormed = 0;
    private static TreeSet<String> allPossWords = new TreeSet<String>();

    public static void main(String[] args) throws Exception
    {
        Scanner dfile = new Scanner(new FileReader(args[0]));
        TreeSet<String> dictionary = new TreeSet<String>();

        while(dfile.hasNext())
        {
            dictionary.add(dfile.next());
        }
        dfile.close();

        Scanner bfile = new Scanner(new FileReader(args[1]));
        int r = bfile.nextInt();
        int c = r;
        String[][] board = new String[r][c];

        for (int i = 0; i < r; i++) 
            for (int j = 0; j < c; j++)
                board[i][j] = bfile.next();

        for(int row = 0; row < board.length; row++)
            for(int col = 0; col < board[row].length; col++)            
                depthFirstSearch(board, row, col, "");

        for(String possWords : allPossWords)
            System.out.println(possWords);
    }

    public static void depthFirstSearch(String[][] board, int r, int c, String word)
    {
        word = word.concat(board[r][c]);
        ++numWordsFormed;
        allPossWords.add(word);

        if(((r-1) >= 0) && (Character.isLowerCase(board[r-1][c].charAt(0)))){
            board[r][c] = board[r][c].toUpperCase();
            depthFirstSearch(board, r-1, c, word);
            board[r][c] = board[r][c].toLowerCase();
        }

        if(((r-1) >= 0) && ((c+1) < board[r-1].length) && (Character.isLowerCase(board[r-1][c+1].charAt(0)))){
            board[r][c] = board[r][c].toUpperCase();
            depthFirstSearch(board, r-1, c+1, word);
            board[r][c] = board[r][c].toLowerCase();
        }

        if(((c+1) < board[r].length) && (Character.isLowerCase(board[r][c+1].charAt(0)))){
            board[r][c] = board[r][c].toUpperCase();
            depthFirstSearch(board, r, c+1, word);
            board[r][c] = board[r][c].toLowerCase();
        }

        if(((r+1) < board.length) && ((c+1) < board[r+1].length) && (Character.isLowerCase(board[r+1][c+1].charAt(0)))){
            board[r][c] = board[r][c].toUpperCase();
            depthFirstSearch(board, r+1, c+1, word);
            board[r][c] = board[r][c].toLowerCase();
        }

        if(((r+1) < board.length) && (Character.isLowerCase(board[r+1][c].charAt(0)))){
            board[r][c] = board[r][c].toUpperCase();
            depthFirstSearch(board, r+1, c, word);
            board[r][c] = board[r][c].toLowerCase();
        }

        if(((r+1) < board.length) && ((c-1) >= 0) && (Character.isLowerCase(board[r+1][c-1].charAt(0)))){
            board[r][c] = board[r][c].toUpperCase();
            depthFirstSearch(board, r+1, c-1, word);
            board[r][c] = board[r][c].toLowerCase();
        }

        if(((c-1) >= 0) && (Character.isLowerCase(board[r][c-1].charAt(0)))){
            board[r][c] = board[r][c].toUpperCase();
            depthFirstSearch(board, r, c-1, word);
            board[r][c] = board[r][c].toLowerCase();
        }

        if(((r-1) >= 0) && ((c-1) >= 0) && (Character.isLowerCase(board[r-1][c-1].charAt(0)))){
            board[r][c] = board[r][c].toUpperCase();
            depthFirstSearch(board, r-1, c-1, word);
            board[r][c] = board[r][c].toLowerCase();
        }
    }

}
4

1 回答 1

1

首先，实现一个 Trie，并在初始化时为它写一个字典。任何单词的查找时间都是确定性的，因为单词的长度是从 Trie 的空根到叶子的最后一个字母的遍历时间。

然后，从 Trie 的结构中，创建一个启发式。

于 2018-04-12T20:25:28.977 回答