カスタムクラスベクトルで検索する

Question

私はこのコードをLeetCodeから練習して、C++でうまくいくようにしています。残念ながら、私は '見つける'を正しく動作させることができません。
このコードは二度同じ文字を訪問することなく、タイプCHAR（すなわちボード）のベクトルのベクトルからワードを検索するために使用される（visitedSoFarは、xを追跡し、文字visitedSoFarのY位置）。
クラスノードのベクトルは、これまで訪問した位置を格納するために使用されます。
は、ここで私が書いたコードスニペットです：私は検索をコメントした場合

class Node{ 
    private: 
     int x; 
     int y; 

    public: 
     Node(int a, int b):x(a),y(b){}; 
     bool operator==(Node newNode){ 
      if(this->x == newNode.x && this->y == newNode.y) 
       return true; 
      else 
       return false; 
     } 
}; 

class Solution { 
public: 
    bool exist(vector<vector<char>>& board, string word) { 
     vector <Node> visitedSoFar; 

     for(int r =0; r< board.size(); r++){ 
      for(int c=0; c<board[r].size(); c++){ 
       if(board[r][c] == word.at(0)){ 

       if(search(board, word, visitedSoFar, board[r].size(), r, c)) 
        return true; 
       } 
      } 
     } 
     return false; 
    } 

    private: 
    bool search(vector<vector<char>>& board, string word, vector<Node>& visitedSoFar, int size, int r, int c){ 
     Node newNode(r,c); 
     visitedSoFar.push_back(newNode); 

     if(word.size() == 1) 
      return true; 

     Node toSearch1(r-1,c); 
     if(r-1 >= 0 && find(visitedSoFar.begin(), visitedSoFar.end(), toSearch1) == visitedSoFar.end()){ 
      if(board[r-1][c] == word.at(1)) 
       if(search(board, word.substr(1), visitedSoFar, size, r-1, c)) 
        return true; 
     } 

     Node toSearch2(r+1,c); 
     if(r+1 < size && find(visitedSoFar.begin(), visitedSoFar.end(), toSearch2) == visitedSoFar.end()){ 
      if(board[r+1][c] == word.at(1)) 
       if(search(board, word.substr(1), visitedSoFar, size, r+1, c)) 
        return true; 
     } 

     Node toSearch3(r,c-1); 
     if(c-1 >= 0 && find(visitedSoFar.begin(), visitedSoFar.end(), toSearch3) == visitedSoFar.end()){ 
      if(board[r][c-1] == word.at(1)) 
       if(search(board, word.substr(1), visitedSoFar, size, r, c-1)) 
        return true; 
     } 

     Node toSearch4(r,c+1); 
     if(c+1 < size && find(visitedSoFar.begin(), visitedSoFar.end(), toSearch4) == visitedSoFar.end()){ 
      if(board[r][c+1] == word.at(1)) 
       if(search(board, word.substr(1), visitedSoFar, size, r, c+1)) 
        return true; 
     } 
     visitedSoFar.pop_back(); 
     return false; 
    } 
}; 

は、私が正しい出力を得るが、これはすべてのテストケースのために動作しないでしょう。

ありがとうございます。

編集
文は（R + 1）と（c + 1）のためにサイズに対してチェックする場合は修正方法の検索では、。

編集
単語は「隣接」セルが水平方向または垂直方向に隣接するもので順次隣接するセルの文字から構成することができます。同じ文字セルを複数回使用することはできません。

編集
デザインエラー：検索操作は、それに検索を続行する（ノードがこれまでに訪問されていないことを示す）を見つけることができないはずです。したがって、！= visitedSoFar.end（）ではなく、== visitedSoar.end（）に変更されました。

Answer 1

ソリューションのよりシンプルなデザインを使用する必要があります。 すべてのボードポイントをチェックするという考えは、おそらく不必要な作業でしょうか？あなたのアプローチを使用して、作業がすでに完了しているかどうかを常に確認しています。このチェックには、すべての検索手順のためにボードを介した線形検索が含まれます（すべてのノードはしばらくの間保存されます）。これは、実行する作業がほぼ同じであるため、ほとんどそれをチェックすることを避けることができます。

したがって、高速にコード化されたソリューションは、このようになります。

bool row_contains_word(vector<char> const& row, string word) 
{ 
    if(word.size() > row.size()) 
    throw std::invalid_argument("Word is longer then the row!!"); 

    // linear search for the word in board 
    for(int i = 0; i < row.size() - word.size(); ++i) // start point 
    { 
    // check realtive to the start point if its the word there 
    for(int j = 0; j < word.size(); ++j) 
    { 
     if(row[i+j] != word[j]) 
     break; // we can continue to check the next position 
     // last position we check here, and match means its the word 
     else if(j == (word.size() - 1) && row[i+j] == word[j]) 
     return true; 
    } 
    } 
    return false; 

この機能を（私はその本当に良い方法は、それを達成するために考えていけないが、ちょうど例を持っている）を使用することができますが、単純にループ：

コメントで述べたように

for(int r = 0; r < board.size(); ++r) 
{ 
    if(row_contains_word(board[r], word)) 
    return true; 
} 
// and same with colums as well 

、ソリューションありえませんクラスの候補者。 それは次のように記述できます。

namespace Solution 
{ 
    bool search(vector<vector<char>> const& board, string word); // implementaion follows 

    namespace // anonymous namespace, not accessible from the outside world, but only this compilation unit(.cpp file) 
    { 
    bool row_contains_word(vector<char> const& row, string word); 
    bool col_contains_word(/*vector<char> const& row,*/ string word); // this needs more work, since the col is a little different 
    } 
} 

これは言葉がボードに含まれているかどうかの決定の界面からの検索から実装を隠すことができます。