我如何打印 BFS 路径本身而不是这个字梯的路径长度？

Question

我收到了实施广度优先搜索的单词阶梯的启动器 code/algorithm。该程序采用单词词典，但我对其进行了修改以采用输入文件。我得到的算法打印出从源词到目标词的路径长度 ex：如果需要 4 次转换才能到达目标词，它将打印 4。我想打印路径本身。例如：如果源词是 "TOON" 并且源词是 "PLEA" 它应该打印 "TOON -> POON -> POIN -> PLIN -> PLIA -> PLEA"

到目前为止，我已经尝试添加一个循环，将队列中的单词附加到向量，然后 returns 向量，但我收到一个我不明白的错误。

main.cpp:42:18: error: no matching member function for
    call to 'push_back'
transformation.push_back(Q.front());

我已经被这个问题困扰了几天，所以任何帮助将不胜感激。我是 C++ 的新手，所以请原谅我的任何错误。

这是代码

#include<bits/stdc++.h>
#include <iostream>

using namespace std;

// To check if strings differ by exactly one character 
bool nextWord(string & a, string & b) {
  int count = 0; // counts how many differeces there
  int n = a.length();

  // Iterator that loops through all characters and returns false if there is more than one different letter 
  for (int i = 0; i < n; i++) {
    if (a[i] != b[i]) {
      count++;
    }

    if (count > 1) {
      return false;
    }
  }
  return count == 1 ? true : false;
}

// A queue item to store the words
struct QItem {
  string word;
};

// Returns length of shortest chain to reach 'target' from 'start' 
// using minimum number of adjacent moves. D is dictionary 
int wordLadder(string & start, string & target, set < string > & D) {
  vector < string > transformation;

  // Create a queue for BFS and insert 'start' as source vertex 
  queue < QItem > Q;
  QItem item = {
    start
  }; // Chain length for start word is 1 
  Q.push(item);
  transformation.push_back(Q.front());

  // While queue is not empty 
  while (!Q.empty()) {

    // Take the front word 
    QItem curr = Q.front();
    Q.pop();

    // Go through all words of dictionary 
    for (set < string > ::iterator it = D.begin(); it != D.end(); it++) {
      // Proccess the next word according to BFS
      string temp = * it;
      if (nextWord(curr.word, temp)) {
        // Add this word to queue from the dictionary
        item.word = temp;
        Q.push(item);

        // Pop from dictionary so that this word is not repeated
        D.erase(temp);

        // If we reached target 
        if (temp == target) {
          return 0;
        }
      }
    }
  }

  return 0;
}

string start;
string target;

// Driver program 
int main() {
  // make dictionary 
  std::ifstream file("english-words.txt");
  set < string > D;

  copy(istream_iterator < string > (file),
    istream_iterator < string > (),
    inserter(D, D.end()));

  cout << endl;
  cout << "Enter Start Word" << endl;
  cin >> start;
  cout << "Enter Target Word" << endl;
  cin >> target;

  cout << wordLadder(start, target, D);
  return 0;
}

Answer 1

您试图将错误的对象附加到 vector<string>

改变

transformation.push_back(Q.front());

到

transformation.push_back(Q.front().word);

我如何打印 BFS 路径本身而不是这个字梯的路径长度？

How can I print the BFS path itself rather than the length of the path from this word ladder?

c++

queue

vector

breadth-first-search