0

4x4 グリッド (Boggle) 上の隣接するタイルで作成できるすべての単語を見つけるアプリケーションを作成しています。文字列を入力できるところまで来て、アルゴリズムは利用可能なすべての単語を最適な時間内に見つけます。ただし、有効な単語だけでなく、ボード上のマスの位置も知る必要があります。

これがメインの Game クラスです。アルゴリズムは再帰的に 1 つの文字で始まり、その文字とその隣の文字で始まる単語が存在するかどうかを確認します。単語が存在しない場合、パスはブロックされ、アルゴリズムは次の文字に進みます。その接頭辞を持つ単語が存在する場合は、その隣人と同じことを行います。

import java.io.IOException;
import java.util.ArrayList;

public class Game {
private final int boardSize = 4;
private BoardSquare[][] squares;
private ArrayList<String> validWords;
private static WordTree trie;
private static int counter = 0;
private DevRunner runner;

public Game(String letters) throws IOException{
    validWords = new ArrayList<String>();
    runner = new DevRunner();
    trie = new WordTree();
    squares = new BoardSquare[boardSize][boardSize];
    for (int y=0; y<boardSize; y++){
        for (int x=0; x<boardSize; x++){
            squares[x][y] = new BoardSquare(letters.charAt(y*boardSize + x), y*boardSize + x);
        }
    }
    for (int y=0; y<boardSize; y++){
        for (int x=0; x<boardSize; x++){
            for (int a=-1; a<2; a++){
                for (int b=-1; b<2; b++){
                    if (a == 0 && b == 0) continue;
                    if (x+b < 0 || y+a < 0) continue;
                    if (x+b > boardSize-1 || y+a > boardSize-1) continue;
                    squares[x][y].addNeighbor(squares[x+b][y+a]);
                }
            }
        }
    }
    getPossibleCombinations();
    System.out.println(counter + " words found.");
}

public void getPossibleCombinations(){
    for (int y=0; y<boardSize; y++){
        for (int x=0; x<boardSize; x++){
            doNeigh(squares[x][y], "", new ArrayList<Integer>());
        }
    }
}

public void doNeigh(BoardSquare square, String path, ArrayList<Integer> locations) {
    square.setIsActive(true);
    path += square.getData();
    locations.add(square.getPosition());
    if (trie.has(path) != 0){
        for (BoardSquare neighbor : square.getNeighbors()){
            if (!neighbor.getIsActive()){
                doNeigh(neighbor, path, locations);
                };
            }
        }
    if (trie.has(path) == 1 && !validWords.contains(path)){
        System.out.print(path + " is a word! (");
        validWords.add(path);
        for (int i : locations){
            System.out.print(i + " -> ");
        }
        System.out.print("\n");
        sendWord(path);
        counter++;
    }
    square.setIsActive(false);
}

public void sendWord(String s){

}

public static void main(String[] args){
    try {
        long t1 = System.currentTimeMillis();
        Game g = new Game("SIOZTRTEBAINERLA");
        long t2 = System.currentTimeMillis();
        System.out.println("The algorithm took " + Long.toString(t2-t1) + " milliseconds to complete.");
    } catch (IOException e) {
        e.printStackTrace();
    }
}
}

実際の出力:

SITAR is a word! (0 -> 1 -> 2 -> 4 -> 5 -> 8 -> 9 -> 5 -> 2 -> 6 -> 8 -> 10 -> 6 -> 7 -> 11 -> 13 -> 14 -> 15 -> 
SIT is a word! (0 -> 1 -> 2 -> 4 -> 5 -> 8 -> 9 -> 5 -> 2 -> 6 -> 8 -> 10 -> 6 -> 7 -> 11 -> 13 -> 14 -> 15 -> 6 -> 8 -> 10 -> 12 -> 13 -> 8 -> 10 -> 5 -> 6 -> 7 -> 11 -> 14 -> 15 -> 12 -> 14 -> 14 -> 
SIR is a word! (0 -> 1 -> 2 -> 4 -> 5 -> 8 -> 9 -> 5 -> 2 -> 6 -> 8 -> 10 -> 6 -> 7 -> 11 -> 13 -> 14 -> 15 -> 6 -> 8 -> 10 -> 12 -> 13 -> 8 -> 10 -> 5 -> 6 -> 7 -> 11 -> 14 -> 15 -> 12 -> 14 -> 14 -> 5 -> 2 -> 3 -> 6 -> 7 -> 4 -> 6 -> 8 -> 9 -> 10 -> 6 -> 7 -> 9 -> 11 -> 6 -> 7 -> 14 -> 15 -> 13 -> 14 -> 15 ->

期待される出力:

SITAR is a word! (0 -> 1 -> 4 -> 9 -> 5 ->
SIT is a word! (0 -> 1 -> 4 ->
SIR is a word! (0 -> 1 -> 5 ->
...

doNeigh() メソッドを使用しString pathて再帰的にビルドできる理由がわかりませんが、同じ方法で正方形の位置の配列リストを作成しようとすると、構成されていない正方形の束が含まれます言葉。

どんな助けでも大歓迎です、ありがとう。

4

1 に答える 1

0

の最後にある から最後の要素を削除する必要がlocationsありdoNeigh()ます。そうしないと、このパスは無限に大きくなります。

于 2015-12-20T17:11:50.740 に答える