Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

商人过河问题扩展

昨天讨论了商人过河问题的基本解法和算法：
将算法应用于实际——商人过河问题 – 掘金 (juejin.cn)

3个商人、3个随从的话商人可以保命，那n个商人，m个随从呢？

很显然，我们上期的算法不是专门为3个商人和3个随从量身定做的。

在上期的代码中，我们只要给相应的数组扩容，然后再修改mNum,fNum，就能求解任意数量的商人过河问题。（当然不能超过c++内存限制啦）

比如，在我写的代码中，我将全局变量mNum和fNum改成了4和4，最后程序遗憾地输出了：

无解！
复制代码

所有的答案？

既然有解，那我为什么不顺便输出所有的解呢？

考虑到我们用DFS的方法，我选择了树这一数据结构来保存所有的可行路径。

首先树的结点的结构体如下，我们用vector来保存所有的结点：

struct State
{
   int m;
   int f;
   int b; // 0代表运向左边，1代表运向右边
   vector<int> sons;//储存在数组中的索引
};
vector<State> trackTree;
复制代码

我们来递归的研究这一问题：

假设DFS函数的输入是一个图的结点。

如果该状态不能到达最终状态，则输出0；如果能够到达最终状态，则生成一个路径树，返回树根的索引。

树的结构如下：

我们进入一个DFS函数后，他先判断自己本身是不是终点。如果是，那么他直接在vector中生成一个结点并返回索引，因为节点本身即是路径树。

如果不是终点的话，他会遍历所有的邻接结点，依次执行DFS。 如果存在一次DFS不返回0，那么他就会生成一个结点，作为返回的结点的父节点。

在把所有的邻接结点都遍历完之后，如果所有的DFS都返回0，那就说明无解，它自己也可以返回0了。如果存在不为0的返回值，说明有解，并且已经生成好了一个路径树。 返回索引即可。

注意！请设置一个found[m][f][b]数组，进入DFS时令相应状态的found为1，即将返回时令其为0.否则很容易出现之后的递归会回到这次递归的结点，从而产生无数个回路！

输出格式

写好代码后，我们的计算机可爱的帮我们求出了所有可行的状态路径：

请分别输入商人数、随从数、船只容量:
4 2 2
(0 0 0) (0 0 1) 
(0 1 0) (0 1 1)
(0 2 0) (0 2 1)
(1 0 0) (1 0 1)
(1 1 0) (1 1 1)
(2 0 0) (2 0 1)
(2 1 0) (2 1 1)
(2 2 0) (2 2 1)
(3 1 0) (3 1 1)
(3 2 0) (3 2 1)
(4 0 0) (4 0 1)
(4 1 0) (4 1 1)
(4 2 0) (4 2 1)
所有状态的数量：26
(4,2,0) (0,2,1) (4,1,0) (1,1,1) (3,2,0) (2,1,1) (2,2,0) (2,2,1) (2,1,0) (3,2,1) (1,1,0) (4,1,1) (0,2,0) (4,2,1) 
(4,2,0) (0,2,1) (4,1,0) (1,1,1) (3,2,0) (2,1,1) (2,2,0) (2,2,1) (2,1,0) (3,2,1) (1,1,0) (4,2,1)
(4,2,0) (0,2,1) (4,1,0) (1,1,1) (3,2,0) (2,1,1) (2,2,0) (2,2,1) (2,1,0) (3,2,1) (2,0,0) (4,2,1)
(4,2,0) (0,2,1) (4,1,0) (1,1,1) (3,2,0) (2,1,1) (2,2,0) (2,2,1) (2,1,0) (4,1,1) (0,2,0) (4,2,1) 
(4,2,0) (0,2,1) (4,1,0) (1,1,1) (3,2,0) (2,1,1) (2,2,0) (2,2,1) (2,1,0) (4,1,1) (1,1,0) (3,2,1) (2,0,0) (4,2,1)
(4,2,0) (0,2,1) (4,1,0) (1,1,1) (3,2,0) (2,1,1) (2,2,0) (2,2,1) (2,1,0) (4,1,1) (1,1,0) (4,2,1)
(4,2,0) (0,2,1) (4,1,0) (1,1,1) (3,2,0) (2,1,1) (2,2,0) (2,2,1) (3,1,0) (3,1,1) (2,1,0) (3,2,1) (1,1,0) (4,1,1) (0,2,0) (4,2,1) 
(4,2,0) (0,2,1) (4,1,0) (1,1,1) (3,2,0) (2,1,1) (2,2,0) (2,2,1) (3,1,0) (3,1,1) (2,1,0) (3,2,1) (1,1,0) (4,2,1)
(4,2,0) (0,2,1) (4,1,0) (1,1,1) (3,2,0) (2,1,1) (2,2,0) (2,2,1) (3,1,0) (3,1,1) (2,1,0) (3,2,1) (2,0,0) (4,2,1)
...
复制代码

具体代码如下：

/*
首先解决问题一：最简单的形式，3个商人(m)与3个随从(f)过河
拥有可行的状态，拥有状态转移的方式
从初始状态转移至最终状态
m指河左边的商人数，f是随从数，b=0代表船在左边，1在右边
*/
#include <iostream>
#include <vector>
using std::cin;
using std::cout;
using std::string;
using std::vector;
const int maxn = 1000 + 7;
int found[maxn][maxn][2];
int able[maxn][maxn][2];
struct State
{
   int m;
   int f;
   int b; // 0代表运向左边，1代表运向右边
   vector<int> sons;
};
vector<State> trackTree;
vector<int> trackStack;
int mNum, fNum, bCap;
int stateNum;
//注意：在状态转移时不能转移回去，否则可能无限递归
//给经过的状态设置标记
// DFS返回0代表没有可行路径，返回正数代表结点在trackTree里的下标
int DFS(int m, int f, int b)
{
   found[m][f][b] = 1;
   int index;
   // trackTree.push_back(State{m, f, b, vector<int>()});
   // index = trackTree.size() - 1;
   if (m == 0 && f == 0 && b == 1)
   {
      found[m][f][b] = 0;
      trackTree.push_back(State{m, f, b, vector<int>()});
      index = trackTree.size() - 1;
      return index;
   }
   int flag = 0;
   for (int d1 = 0; d1 <= bCap; d1++)
   {
      for (int d2 = 0; d2 <= bCap; d2++)
      {
         if (d1 + d2 <= bCap && d1 + d2 > 0)
         {
            int m1, f1, b1;
            if (b == 1)
            {
               m1 = m + d1, f1 = f + d2, b1 = 0;
               if (!(m1 <= mNum && f1 <= fNum && able[m1][f1][b1] && !found[m1][f1][b1]))
                  continue;
            }
            else
            {
               m1 = m - d1, f1 = f - d2, b1 = 1;
               if (!(m1 >= 0 && f1 >= 0 && able[m1][f1][b1] && !found[m1][f1][b1]))
                  continue;
            }
            int ret = 0;
            if (ret = DFS(m1, f1, b1))
            {
               //保证只执行一次
               if (flag == 0)
               {
                  flag = 1;
                  trackTree.push_back(State{m, f, b, vector<int>()});
                  index = trackTree.size() - 1;
               }
               trackTree[index].sons.push_back(ret);
            }
         }
      }
   }
   found[m][f][b] = 0;
   return flag == 1 ? index : 0;
}
void setEnableState()
{
   for (int m = 0; m <= mNum; m++)
   {
      for (int f = 0; f <= fNum; f++)
      {
         int m1 = mNum - m, f1 = fNum - f;
         //任何一边，商人比随从多或者商人为0为可行状态
         if ((m >= f || m == 0) && (m1 >= f1 || m1 == 0))
         {
            able[m][f][0] = able[m][f][1] = 1;
            printf("(%d %d %d) ", m, f, 0);
            printf("(%d %d %d) \n", m, f, 1);
            stateNum += 2;
         }
      }
   }
}
void Print(int index)
{
   trackStack.push_back(index);
   if (trackTree[index].sons.size() == 0)
   {
      //此时栈里已经是一条完整的track
      for (auto i : trackStack)
      {
         auto t = trackTree[i];
         printf("(%d,%d,%d) ", t.b == 1 ? mNum - t.m : t.m, t.b == 1 ? fNum - t.f : t.f, t.b);
      }
      putchar('\n');
      trackStack.pop_back();
      return;
   }
   for (auto son : trackTree[index].sons)
   {
      Print(son);
   }
   trackStack.pop_back();
   return;
}
int main()
{
   cout << "请分别输入商人数、随从数、船只容量:\n";
   cin >> mNum >> fNum >> bCap;
   setEnableState();
   cout << "所有状态的数量：" << stateNum << '\n';
   trackTree.push_back(State()); //添加一条空数据
   if (DFS(mNum, fNum, 0))
   {
      for (int i = 0; i < trackTree.size(); i++)
         if (trackTree[i].b == 0 && trackTree[i].f == fNum && trackTree[i].m == mNum)
            Print(i);
   }
   else
      cout << "无解！\n";
   return 0;
}
复制代码