c++ - Word Solver - 全方向

Question

すべての方向の単語ソルバーを作成しました。単語を水平方向、垂直方向、逆方向に検索します。ただし、すべての方向に移動するのに問題があります。したがって、「こんにちは」を次のように使用します。

H  E  i  l
x  L  p  q
c  L  O  m

誰でもそれを行う方法を教えてもらえますか? これが単語を検索する私のアルゴリズムです（C ++で）：

/*
 * For loops that search each row, each column in all 8 possible directions.
 */
void Scramble::solve() {

cout << "Output:" << endl;

for (int row = 0; row < getRows(); row++) {
    for (int col = 0; col < getCols(); col++)
        for (int rowDir = -1; rowDir <= 1; rowDir++)
            for (int colDir = -1; colDir <=1; colDir++)
                if (rowDir != 0 || colDir != 0)
                    findWords(row, col, rowDir, colDir);
}
}

/*
 * Finds the matches in a given direction. Also calls verifyWord() to verify that the
 * current sequence of letters could possibly form a word. If not, search stops.
 */
void Scramble::findWords(int startingRow, int startingCol, int rowDir, int colDir) {

int searchResult;
string sequence = "";
sequence = sequence + wordsArr[startingRow][startingCol];

for (int i = startingRow + rowDir, j = startingCol + colDir; i >= 0 && j >= 0
&& i < getRows() && j < getCols(); i = i + rowDir, j = j + colDir) {

    sequence = sequence + wordsArr[i][j];

    if (sequence.length() >= 3) {

        searchResult = verifyWord(words, sequence);

        if ((unsigned int)searchResult == words.size())
            break;

        if (words[searchResult].rfind(sequence) > words[searchResult].length())
            break;

        if (words[searchResult] == (sequence))
            cout << sequence << endl;
    }
}
}

/*
 * Performs the verifyWord search method.
 * Searches the word to make sure that so far, there is possibly that the current sequence
 * of letter could form a word. That is to avoid continuing to search for a word
 * when the first sequence of characters do not construct a valid word in the dictionary.
 *
 * For example, if we have 'xzt', when this search is done it prevents the search
 * to continue since no word in the dictionary starts with 'xzt'
 */
int Scramble::verifyWord(vector<string> words, string str) {

int low = 0;
int mid = 0;
int high = words.size();

while (low < high) {

    mid = (low + high) / 2;

    if (str > words[mid]) {
        low = mid + 1;
    }

    else if (str < words[mid]) {
        high = mid - 1;
    }

    else
        return mid;
}
}

Answer 1

これは興味深い考え方です。単語を見つけることは、迷路を解くことに似ています。'start' と 'end' は探している単語の最初と最後に対応し、'dead end' はパスと単語の不一致に対応し、'success' はパスに沿った文字列が一致した場合です。一致です。

ここでの朗報は、迷路を解くアルゴリズムに関するリソースがたくさんあることです。私がよく知っていて、実装するのがそれほど難しくない特定のアルゴリズムの 1 つは、バックトラッキングを使用した再帰です。

これが問題に対して機能するためには、明らかにいくつかの変更を加える必要があります。たとえば、開始点がどこにあるかはわかりませんが、幸いなことに問題ではありません。可能なすべての開始位置を確認できますが、それらの多くは、不一致のために最初のステップで破棄されます。

Answer 2

各文字が隣接するすべての文字に接続されているグラフのように扱い、各文字から開始して深さ/幅優先探索を実行し、その文字が探している次の文字と等しいノードのみを受け入れます。

Answer 3

これは私が書いた簡単な単語調査プログラムです --->

#include<iostream>

using namespace std;

int main()
{
    int a, b, i, j, l, t, n, f, g, k;
    cout<<"Enter the number of rows and columns: "<<endl;               
    cin>>a>>b;                                                              //Inputs the number of rows and columns
    char mat[100][100], s[100];
    cout<<"Enter the matrix: "<<endl;
    for (i = 0; i < a; i++) for (j = 0; j < b; j++) cin>>mat[i][j];         //Inputs the matrix
    cout<<"Enter the number of words: "<<endl;
    cin>>t;                                                                 //Inputs the number of words to be found
    while (t--)
    {
        cout<<"Enter the length of the word: "<<endl;
        cin>>n;                                                             //Inputs the length of the word
        cout<<"Enter the word: "<<endl;
        for (i = 0; i < n; i++) cin>>s[i];                                  //Inputs the word to be found
        for (i = 0; i < a; i++)                                         //Loop to transverse along i'th row
        {
            for (j = 0; j < b; j++)                                     //Loop to transverse along j'th column
            {
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, g++);          //Loop to find the word if it is horizontally right
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" right"<<endl;
                    goto A;
                }
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, g--);      //Loop to find the word if it is horizontally left
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" left"<<endl;
                    goto A;
                }
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, f++);      //Loop to find the word if it is vertically down
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" down"<<endl;
                    goto A;
                }
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, f--);      //Loop to find the word if it is vertically up
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" up"<<endl;
                    goto A;
                }
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, f++, g++); //Loop to find the word if it is down right
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" down right"<<endl;
                    goto A;
                }
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, f--, g--); //Loop to find the word if it is up left
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" up left"<<endl;
                    goto A;
                }
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, f++, g--); //Loop to find the word if it is down left
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" down left"<<endl;
                    goto A;
                }
                f = i;
                g = j;
                for (k = 0; s[k] == mat[f][g] && k < n; k++, f--, g++); //Loop to find the word if it is up right
                if (k == n)
                {
                    cout<<"The coordinates and direction are ---> "<<j+1<<","<<i+1<<" up right"<<endl;
                    goto A;
                }
            }
        }
        A:;                                                             //If the word has been found the program should reach this point to start the search for the next word
    }
    return 0;
}

私のプログラムでは、最初に単語の最初の文字をチェックし、次に後続の文字をチェックします。単語が見つかった場合は、単語の開始座標と単語が見つかった方向を出力します。

Answer 4

1) 現在、あなたの関数は各点から始まる直線でsolve()単語を探します: これはあなたが意図したものですか? 「こんにちは」がサンプルマトリックスに直線として表示されないため、私は尋ねるだけです:

H  E  i  l
x  L  p  q
c  L  O  m

直線的な単語のみが必要な場合は問題ありません(これが、これらのパズルがとにかく機能することを常に理解している方法です) が、実際に蛇のように単語を見つけたい場合は、Zilchonum のような再帰検索と BlueRaja は、良い賭けになると示唆しています。すでに使用した文字にループバックしないように注意してください。

2) どちらの場合も、関数にはいくつかの問題があります。少なくとも、ループverifyWord()を終了する場合に何らかの値を返す必要があります。while (low < high)

それでも、あなたが望んでいることはまだうまくいきません: たとえば、辞書に が含まれているとし{"ant", "bat" "hello", "yak", "zoo"}ます。verifyWord()str="hel"

step  low   mid  high
 0     0     0     5   // initialise
 1     0     2     5   // set mid = (0+5)/2 = 2... words[2] == "hello" 
 2     0     2     1   // "hel" < "hello" so set high = mid - 1
 3     0     0     1   // set mid = (0+1)/2 = 0... words[0] == "ant"
 4     1     0     1   // "hel" > "ant" so set low = mid + 1     
 5  // now (low<high) is false, so we exit the loop with mid==0

「hel」と「hello」を比較するよりも、辞書内の単語を str と同じ長さに切り詰める方がよいでしょstrうword[mid].substr(0,str.length())。