野人过河问题，回溯算法

Question

#ifndef HEAD_H_
#define HEAD_H_
#include<vector>
using namespace std;

class Guohe
{
public:
    Guohe(int xx, int yy, bool zz) :x(xx), y(yy), z(zz) {} //构造函数
    bool operator==(const Guohe& g) const;         //重载==运算符
    int getx();       //获取船所在岸边野人数量
    int gety();       //获取船所在岸边传教士数量
    bool getz() { return z; };        //获取船的位置
    bool safe(Guohe& g) const;     //判断状态是否安全
    void yidong(Guohe& g);   //船的移动
    friend void gh(Guohe& a, const Guohe& b);  //友元函数
private:
    int x, y;   //野人、传教士数量(左岸)
    bool z;     //true为船在左岸，false为船在右岸
};


class Gc
{
public:
    Gc(int x, int y);
    Gc();
    void weicha(const int x, const int y);   //末尾添加元素
    int ssize() { return a.size(); }
    bool operator==(const Gc& g) const;     //重载==运算符
    void pop();       //删除最后一个元素
    void print();     //输出函数
    void fuzhi(const Gc& g);       //复制函数
private:
    vector<int>a, b;
};

int Guohe::getx()
{
    if (z)
        return x;
    else
        return 3 - x;
}

int Guohe::gety()
{
    if (z)
        return y;
    else
        return 3 - y;
}

bool Guohe::operator==(const Guohe& g) const
{
    if (this->x == g.x && this->y == g.y)
        return true;
    else
        return false;
}

bool Guohe::safe(Guohe& g) const
{
    bool b = false;
    if (g.y == 0 || g.y == 3)
        b = true;
    else
    {
        if (g.x <= g.y && (3 - x <= 3 - y))
            b = true;
    }
    return b;
}

void Guohe::yidong(Guohe& g)
{
    if (g.z)
        g.z = false;
    else
        g.z = true;
}




Gc::Gc(int x, int y)
{
    a.push_back(x);
    b.push_back(y);
}

Gc::Gc()
{
    a.push_back(0);
    b.push_back(0);
}

bool Gc::operator==(const Gc& g) const
{
    if (this->a == g.a && this->b == g.b)
        return true;
    else
        return false;
}

void Gc::weicha(const int x, const int y)
{
    a.push_back(x);
    b.push_back(y);
}

void Gc::pop()
{
    a.pop_back();
    b.pop_back();
}

void Gc::print()
{
    for (int i = 1; i < a.size(); i++)
    {
        //cout << b[i] << "  " << a[i] << endl;
        if (i % 2 == 1)
            cout << "左岸到右岸，传教士过去" << b[i] << "人,野人过去" << a[i] << "人" << endl;
        else
            cout << "右岸到左岸，传教士过去" << b[i] << "人,野人过去" << a[i] << "人" << endl;
    }
}

void Gc::fuzhi(const Gc& g)
{
    this->a = g.a;
    this->b = g.b;
}
#endif


#include<iostream>
#include"head.h"

int m1, m2, n1, n2;      //m、n为船上野人和传教士数量

int i = 0;
Gc gc[10];

void gh(Guohe& a, const Guohe& b)
{

    if (a.z)                 //左岸到右岸
    {
        for (m1 = 0; m1 <= 2 && m1 <= a.x; m1++)
        {
            n1 = 2 - m1;
            if (n1 <= a.y)
            {
                a.x = a.x - m1;
                a.y = a.y - n1;
                if (a.safe(a))
                {    
                    gc[i].weicha(m1, n1);
                    //cout << "左岸到右岸，传教士过去" << n1 << "人,野人过去" << m1 << "人   成立" << endl;                    
                    
                    a.yidong(a);
                    if (a == b)
                    {
                        i++;
                        gc[i].fuzhi(gc[i - 1]);
                        return;
                    }
                    gh(a, b);
                    gc[i].pop();
                }
                else
                {
                    a.x = a.x + m1;
                    a.y = a.y + n1;
                }
            }
        }
    }
    else             //右岸到左岸
    {
        for (m2 = 0; m2 <= 2 && m2 <= a.getx(); m2++)
        {
            for (n2 = 0; n2 <= 2 - m2 && n2 <= a.gety(); n2++)
            {
                if (m2 + n2 == 0 || (m2 == m1 && n2 == n1))
                {
                }
                else
                {
                    a.x = a.x + m2;
                    a.y = a.y + n2;
                    if (a.safe(a))
                    {
                        
                        gc[i].weicha(m2, n2);
                        //cout << "右岸到左岸，传教士过去" << n2 << "人,野人过去" << m2 << "人   成立" << endl;                        
                        a.yidong(a);
                        gh(a, b);
                        gc[i].pop();
                    }
                    else
                    {
                        a.x = a.x - m2;
                        a.y = a.y - n2;
                    }
                }
            }
        }
    }
}

int main()
{
    Guohe t(3, 3, true);       //初始状态
    Guohe f(0, 0, false);      //最终状态
    gh(t, f);
    for (int ii = 0; ii <= i; ii++)
    {
        gc[ii].print();
        cout << endl << endl << endl;
    }
    
    return 0;}

有3个野人和3个传教士来到河边渡河，河岸有一条船，每次至多可供2人乘渡，野人和传教士都会划船。在河岸，如果野人人数多于传教士人数，则野人会吃掉传教士。要求输出所有可能的过程。
答案一共有四个结果，为什么我这个只能算出来一种，望各位解惑。

Answer 1

引自强大而免费的R5AI智能助手：r5ai.com

你的代码只能得出一种结果，是因为你只在一开始的时候初始化了一次i，而在后续的递归过程中，当找到一种解法后，i并没有被恢复到原来的值。在你的递归函数中，当找到一个解时，你会增加i的值，但在递归返回后，i的值并没有被减小。这就导致了你在找到一个解之后，下一个解会被写入到下一个gc数组中，而不是覆盖原来的解。因此，你只能得到一种解法。

如果你想获得所有的解法，你可以在找到一个解之后，将i的值减小，然后继续递归。你可以在找到一个解之后，增加i的值，然后递归返回前，再将i的值减小。这样，下一个解就会覆盖之前的解，你就可以得到所有的解法了。

你可以试试在gh函数的if (a == b)语句之后，添加i--;语句，然后看看结果是否符合预期：

if (a == b)
{
    i++;
    gc[i].fuzhi(gc[i - 1]);
    i--;
    return;
}

注意，这只是一个可能的解决方案，你可能还需要对你的代码进行一些其他的调整，以确保它可以正确地找到所有的解法。