0

あなたのおばあさんのために、初めて Java 単語検索プログラムを作成するときが来ました。しかし、文字グリッド内の単語を検索することによってすべての作業を彼女に行わせる代わりに、再帰関数4WaySearchが彼女のためにそれを行います!

唯一の問題は次のとおりです。

グリッド内で一度に開始するときに、考えられるすべての文字の組み合わせを構築する再帰アルゴリズムを概念化するのは難しいと感じています。

これは私がすでに書いたコードで、正しい方向への大きな一歩だと思います:

/* 
* This is the method that calls itself repeatedly to wander it's way
* through the grid using a 4 way pattern,
* creating every possibly letter combination and checking it against a
* dictionary. If the word is found in the dictionary, it gets added to a
* collection of found words.
* 
* Here an example of a 3x3 grid with the valid words of RATZ and BRATZ, but
* the word CATZ isn't valid. (the C is not tangent to the A).
* 
* CXY
* RAT
* BCZ
*
* @param row Current row position of cursor
* @param col Current column position of cursor
*/
private void 4WaySearch(int row, int col) {

    // is cursor outside grid boundaries?
    if (row < 0 || row > ROWS - 1 || col < 0 || col > COLS - 1)
        return; 

    GridEntry<Character> entry = getGridEntry(row, col);

    // has it been visited?
    if (entry.hasBreadCrumb())
        return; 

    // build current word
    currentWord += entry.getElement(); // returns character

    // if dictionay has the word add to found words list
    if (dictionary.contains(currentWord))
        foundWords.add(currentWord);

    // add a mark to know we visited
    entry.toggleCrumb();

    // THIS CANT BE RIGHT
    4WaySearch(row, col + 1);   // check right
    4WaySearch(row + 1, col);   // check bottom
    4WaySearch(row, col - 1);   // check left
    4WaySearch(row - 1, col);   // check top

    // unmark visited
    entry.toggleCrumb();

    // strip last character
    if (currentWord.length() != 0)
        currentWord = currentWord.substring(
        0, 
        (currentWord.length() > 1) ? 
            currentWord.length() - 1 : 
            currentWord.length()
        );
}

私の頭の中では、検索アルゴリズムを再帰的なツリー トラベラル アルゴリズムと同じように視覚化していますが、各ノード (この場合はエントリ) には 4 つの子 (接線エントリ) があり、リーフ ノードはグリッドの境界です。

また、関数への最初のエントリ時のカーソルの位置は、ここで疑似コード化された単純な for ループによって決定されます。

for (int r = 0; r < ROWS; r++)
  for (int c = 0; r < COLS; c++)
    4WaySearch(r,c);
  end for;
end for;

私はこれについてしばらく考えていて、さまざまなアプローチを試みています...しかし、まだ頭を悩ませて機能させることはできません. 誰か私に光を見せてくれませんか? (私とあなたのおばあちゃんのために! :D)

4

3 に答える 3

0

したがって、最初にグリッドを確立する必要があります。この例では、 3x3 を選択しました。必要なのは、グリッド上のすべての有効なポイントを追跡する方法です。コンストラクターとしてPoint2 つの を受け取る というオブジェクトをお勧めします。int次に必要なのは、 aPointと acharで構成されるクラスです。これにより、各 で使用可能な文字を確認できますPoint。

データ構造が整ったので、ゲームの有効な動きを追跡する必要があります。たとえば、私が位置 3,3 (右下隅、ゼロベースの場合は 2,2) にいる場合、私が持っている有効な動きは上または左だけであることを認識する必要があります。これを決定する方法は、私が訪れたすべての場所を 示すSetofを保持することです。これにより、再帰アルゴリズムを終了できます。Point

役立つかもしれない再帰のためのいくつかの疑似コード 

if(!validMovesRemaining)  
     return
else  
    removeValidPosition(pointToRemove);  
    captureLetter(composedObject);
    recurse(pointsRemaining);
于 2011-10-26T20:29:50.030 に答える
0

私がすることは、ツリー構造を構築することです。ノードがそのように定義されている場所

public class Node {
    private String data;
    private int row,col;
    private Node parent;
    public Node(Node parent,int row,int col) {
        this.parent = parent;
        this.col = col;
        this.row = row;
    }
    public boolean hasParent(int row, int col) {
        Node current = this;
        while((current=current.parent)!=null) {
            if(current.row == row && current.col==col)
                return true;
        }
        return false;
    }

    public String toString() {
        Node current = this;
        StringBuffer sb = new StringBuffer();
        do {
            sb.append(current.data);
        }while((current = current.parent)!=null);
        return sb.reverse().toString();
    }
}

ツリーの新しいルート ノードを作成する新しい開始場所があるたびに

for (int r = 0; r < ROWS; r++)
  for (int c = 0; r < COLS; c++)
    4WaySearch(new Node(null,r,c);   //it is the root and has no parent
  end for;
end for;

そして、あなたが行くようにツリーを構築したい

private void FourWaySearch(Node c) {
    if (c.row < 0 || c.row > ROWS - 1 || c.col < 0 || c.col > COLS - 1 || c.hasParent(c.row,c.col))
        return; 
    else {  

        c.data = grid[c.row][c.col];  //get the string value from the word search grid
        if(dictionary.contains(c.toString()))
            foundWords.add(c.toString());
        FourWaySearch(new Node(c,c.row-1,c.col));
        FourWaySearch(new Node(c,c.row,c.col-1));
        FourWaySearch(new Node(c,c.row+1,c.col));
        FourWaySearch(new Node(c,c.row,c.col+1));
    }
}

これは最善の方法ではないかもしれませんが、私にはシンプルで従うのが簡単に思えます。

于 2011-10-26T20:57:24.753 に答える
0

ツリーが進むべき道だと思いますが、他の回答がそれを使用しているようには見えません。私がすることは、（辞書から）探している単語の解析ツリーを構築することです-各文字はノードであり、26の可能な子があり、アルファベットの各文字に1つずつあります（再帰する前nullに子を確認してください)、およびそれが完全な単語かどうかを示すフラグ。各方向を確認し、その方向に移動できるかどうかを確認し、それに応じて移動します。

難しい部分はツリーを構築することであり、再帰的に行うべきではないと言うつもりでしたが、別の考えがありました. ツリーを構築する最良の方法も再帰的です。

これは明らかに単なる概要ですが、うまくいけば、開始するのに十分です。また行き詰まったら、コメントしてください。正しい方向にもっとプッシュできるかどうかを確認します.

于 2011-10-26T21:54:41.530 に答える