1

学習目的で Ruzzle ソルバー Java アプリケーションをプログラミングしようとしています。Ruzzleタイプのマップで「単語を見つける」という問題に少し問題があります。

Ruzzle マップの例 (各セルに 1 文字の 4 行 4 列で構成されています) :

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

  • Map.java

手紙クラス

マップの単一の文字を記述します。そのフィールドは、セルの X 位置と Y 位置、および文字です。

Ruzzlesolver クラス

これがメインクラスです。

  • Ruzzleマップを読み取ります（コンソールに1行ずつ入力）
  • 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の 2 次元配列を操作する方が簡単なので、 のコンストラクタを変更しました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 に答える