c++ - C++永无止境的递归

任务是将给定状态转换为最终状态的步骤最少。例如，如果您输入这样的字符串:



状态看起来像这样(总是6个字符):
2 1 3
4 5 6

您需要将其转换为的状态始终是相同的:
1 2 3
4 5 6

您需要切换数字以获得最终状态，只需水平和垂直切换它们即可。这不是一项艰巨的任务，但是我的永无止境的递归存在问题。请不要在代码上发表评论(使用 namespace std；不使用函数来重复进程等)，因为我还没有完成，所以我需要您帮助我理解为什么这是一个永无止境的递归。

编辑:代码正在工作!

#include <iostream>
#include <map>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int f(string s, map <string, int>& visited, int steps = 0)
{
    string s2 = s;
    vector <int> solutions;
    solutions.push_back(721);
    if(s == "123456")
        return steps;
    else
    {
        swap(s2[0], s2[1]);
        if(visited.find(s2) == visited.end() or steps < visited[s2])
        {
            visited[s2] = steps;
            solutions.push_back(f(s2, visited, steps + 1));
        }
        s2 = s;
        swap(s2[1], s2[2]);
        if(visited.find(s2) == visited.end() or steps < visited[s2])
        {
            visited[s2] = steps;
            solutions.push_back(f(s2, visited, steps + 1));
        }
        s2 = s;
        swap(s2[3], s2[4]);
        if(visited.find(s2) == visited.end() or steps < visited[s2])
        {
            visited[s2] = steps;
            solutions.push_back(f(s2, visited, steps + 1));
        }
        s2 = s;
        swap(s2[4], s2[5]);
        if(visited.find(s2) == visited.end() or steps < visited[s2])
        {
            visited[s2] = steps;
            solutions.push_back(f(s2, visited, steps + 1));
        }
        s2 = s;
        swap(s2[0], s2[3]);
        if(visited.find(s2) == visited.end() or steps < visited[s2])
        {
            visited[s2] = steps;
            solutions.push_back(f(s2, visited, steps + 1));
        }
        s2 = s;
        swap(s2[1], s2[4]);
        if(visited.find(s2) == visited.end() or steps < visited[s2])
        {
            visited[s2] = steps;
            solutions.push_back(f(s2, visited, steps + 1));
        }
        s2 = s;
        swap(s2[2], s2[5]);
        if(visited.find(s2) == visited.end() or steps < visited[s2])
        {
            visited[s2] = steps;
            solutions.push_back(f(s2, visited, steps + 1));
        }
        return *(min_element(solutions.begin(), solutions.end()));
    }
}

int main()
{
    string s;
    cin >> s;
    map <string, int> visited;
    cout << f(s, visited) << endl;
    return 0;
}

输入样例:



样本输出:

最佳答案

代替map <string, bool> visited，您应该使用map <string, int>& visited(注意通过引用传递)。

然后，您可以将if语句更改为:

if(visited.find(s2) == visited.end() || steps < visited[s2])
{
    visited[s2] = steps;
    solutions.push_back(f(s2, visited, steps + 1));
}

这使您在各个深度的路径都可以相互传达一些路径信息。

请注意，您可能可以通过使用迭代解决方案和广度优先搜索来进一步优化，但这应该足以完成我们生活中的某个时间:)

关于c++ - C++永无止境的递归，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26895285/