2

我有一个字符串向量，大小都一样。
我必须构建一个满足某些条件的字符串列表作为解决方案。

伪代码算法将是这样的：

backtrack(N)
if solution_valid()
    print solution
else
    for each word in vector
        if(possible candidate)
           backtrack(N+1)

我迷失了如何实际编写代码。

我不明白如何保存当前的解决方案，将什么样的参数传递给函数......

这是我所拥有的东西，尽管我认为这是完全错误的：

int backtrack(vector<string> &dictionary, vector<string> &solution, int current_row)
{
cout << "current row: "<< current_row <<  " of: " << rows << endl;
if(current_row == rows /*&& square_completed(solution)*/)
{
    vector<string>::iterator word;
    for(word = solution.begin(); word != solution.end(); ++word)
    {
        cout << *word << endl;

    }
    return 0;
}

vector<string>::iterator word;
for(word = dictionary.begin(); word != dictionary.end(); ++word)
{
    backtrack(dictionary,solution,current_row+1);
    solution.push_back(*word);


}

return 1;

}

问题是解决方案在不受控制的情况下不断增长。你能告诉我如何处理它吗？并进行适当的回溯？

4

1 回答 1

1

一个问题是您dictionary在对其进行迭代时进行了修改。修改向量会使该向量的迭代器无效，因此word下次使用它时不再有效。这可能会崩溃或以其他方式失败。但是该erase函数返回一个新的有效迭代器，您可以使用它继续迭代。

此外，您基本上从回溯功能中删除了所有元素，dictionary并且很快就不会有任何元素留在dictionary. 可能您想在递归调用返回后重新添加已删除的元素？

于 2011-02-05T19:31:15.720 回答