C++中的Word Hunting Game算法

Question

我目前正在編寫一個遊戲，在snaky-ways中查找矩陣中的輸入單詞。這裏是遊戲的簡要解釋。

用戶將首先要求輸入包含行的文件名來創建矩陣。創建後，用戶將被要求在該矩陣中輸入要搜索的單詞。搜索僅朝向南部，東部和東南部。如果它找到該單詞，則顯示座標並顯示一些消息。一個例子矩陣如下：

m e r e t z 
e x i t a v 
p p w a b i 
y u u b l l 
a l l l a l 
z k v e l o 

我已成功地搜索詞就像這個矩陣「退出」，但我的問題是，如「僅僅」或「表」字。在我的算法中，我只能搜索在兩個方向上不具有相同字母的單詞。我找不到一個合適的方法來做到這一點。

這是我的代碼的搜索部分。

bool Search(tmatrix<char>& m, tmatrix<int>& c, const string& w, int i, int j, int index) // m is the matrix to search in // w is the word // i and j are coordinates of matrix { 
if(m[i][j] == w[index]) 
{ 
    c[index][0] = i; // c matrix is to keep coordinates of words 
    c[index][1] = j; 

    if(index != w.length()-1) 
    { 
      if((i < m.numrows()-1) && (m[i+1][j] == w[index+1])) 
       return Search(m, c, w, i+1, j, index+1); 
      else if((j < m.numcols()-1) && (i < m.numrows()-1) && (m[i+1][j+1] == w[index+1])) 
       return Search(m, c, w, i+1, j+1, index+1); 
      else if((j < m.numcols()-1) && (m[i][j+1] == w[index+1])) 
       return Search(m, c, w, i, j+1, index+1); 
      else 
       return false; 
    } 
    else 
     return true; 
} 
return false; 

}

int main() 
{ 
    bool IsFound = false;     //to check whether the word is found or not in the matrix 
      tmatrix<int> coord(word.length(), 2); //another matrix to keep coordinates of found word's coordinates. 
                //it works with the index of words and the row index of matrix. 

      for(int i = 0; i < m.numrows(); i++) 
      { 
       for(int j = 0; j < m.numcols(); j++) 
       { 
        int index = 0;  //another variable to keep index number 
        IsFound = Search(m, coord, word, i, j, index);  //searches matrix for word and if found, makes IsFound's return value true 
        if(IsFound) 
        { 
         cout << "The word "<< word << " is found!\n"; 
         cout << "Indices in which this word is found in the matrix are:\n"; 
         for(; index < word.length(); index++) 
         { 
          cout << word[index] << ":\t" << coord[index][0] << "," << coord[index][1] << endl; 
         } 
         break;  //whenever it finds a match in matrix, it finishes search in loops 
        } 
       } 
       if(IsFound) 
        break; 
      } 
} 

這隻能，首先if語句列表上出現的方向。將else if更改爲if對我無效。

Answer 1

void Search(tmatrix<char>& m, tmatrix<int>& c, const string& w, int i, int j, int index) { 
if(m[i][j] == w[index]) 
{ 
    c[index][0] = i; 
    c[index][1] = j; 

    if(index != w.length()-1) 
    { 
      if((i < m.numrows()-1) && (m[i+1][j] == w[index+1])) 
      { 
       Search(m, c, w, i+1, j, index+1); 
      } 
      if((j < m.numcols()-1) && (i < m.numrows()-1) && (m[i+1][j+1] == w[index+1])) 
      { 
       Search(m, c, w, i+1, j+1, index+1); 
      } 
      if((j < m.numcols()-1) && (m[i][j+1] == w[index+1])) 
      { 
       Search(m, c, w, i, j+1, index+1); 
      } 
    } 
    else 
     IsFound = true; 
} } 

更改功能到這個解決我的所有問題。感謝您的評論，他們激勵了我。

Answer 2

只需添加額外的布爾矩陣即可使用該單詞。因此調用搜索之前，設置無效時布爾纔去那個方向，是否「未使用」