Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

The problem of merchants crossing the river expands

Yesterday we discussed the basic solution and algorithm of merchant crossing the river: Applying the algorithm to practice — Merchant crossing the river — digging gold (juejin. Cn)

If 3 merchants and 3 attendants can save the merchant, what about n merchants and m attendants?

Obviously, our last algorithm wasn’t specifically designed for three merchants and three minions.

In the previous code, we could solve any number of merchant crossing problems by simply expanding the corresponding array and then modifying mNum,fNum. (not exceeding the c++ memory limit, of course)

For example, in the code I wrote, I changed the global variables mNum and fNum to 4 and 4, and the program ended up regrettably printing:

No solution!Copy the code

All the answers?

If there are solutions, why don’t I just print out all of them?

Given our DFS approach, I chose a tree data structure to hold all possible paths.

First, the structure of the nodes of the tree is as follows. We use vector to store all nodes:

struct State
{
   int m;
   int f;
   int b; // 0 to the left, 1 to the right
   vector<int> sons;// The index stored in the array
};
vector<State> trackTree;
Copy the code

Let’s study this problem recursively:

Suppose the input of the DFS function is the node of a graph.

If the state cannot reach the final state, 0 is printed. If the final state can be reached, a path tree is generated and the index of the root is returned.

The structure of the tree is as follows:

When we enter a DFS function, he determines whether he is the end. If so, it simply generates a node in the vector and returns the index, since the node itself is the path tree.

If it is not the endpoint, it iterates through all the adjacent nodes and performs DFS in turn. If DFS does not return 0 once, it generates a node as the parent of the returned node.

If all the DFS returns 0 after all the adjacencies have been traversed, then there is no solution and it can return 0 itself. If there is a return value that is not zero, the solution exists and a path tree has been generated. Return the index.

Attention! Please set up a found[m][f][b] array, enter DFS time corresponding state found is 1, will return time it is 0. Otherwise, it’s very easy for a subsequent recursion to return to the node of this recursion, resulting in countless loops!

The output format

After writing the code, our computer lovingly worked out all the possible state paths for us:

Please input the number of merchants, number of attendants and vessel capacity respectively: 4 2 2 (0, 0, 0) (0, 0, 1) (0 0 1) (0, 1, 1) (0, 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) (1, 1) 2 (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 1) (4 2 0) (4 2 1) (4 2 1) (4 2 1) (4 2 1) (4 2 1) 26 (4 0) (0, 2, 1) (4, 0) (1,1,1) (3, 0) (2,1,1) (2, 0) (2, 2, 1) (2, 0) (3, 2, 1) (1, 0) (4,1,1) (0, 0) (4, 2, 1) (4 0) (0, 2, 1) (4, 0) (1,1,1) (3, 0) (2,1,1) (2, 0) (2, 2, 1) (2, 0) (3, 2, 1) (1, 0) (4, 2, 1) (0) (0, 2, 1) (4, 0) ,1,1 (1) (3, 0) (2,1,1) (2, 0) (2, 2, 1) (2, 0) (3, 2, 1) (0, 2) (4, 2, 1) (0) (0, 2, 1) (4, 0) (1,1,1) (3, 0) (2,1,1) (2, 0) (2, 2, 1) (2, 0) (4,1,1) (0, 0) (4, 2, 1) (0) (0, 2, 1) (4, 0) (1,1,1) (3, 0) (2,1,1) (2, 0) (2, 2, 1) (2, 0) ,1,1 (4) (1, 0) (3, 2, 1) (0, 2) (4, 2, 1) (0) (0, 2, 1) (4, 0) (1,1,1) (3, 0) (2,1,1) (2, 0) (2, 2, 1) (2, 0) (4,1,1) (1, 0) (4, 2, 1) (0) (0, 2, 1) (4, 0) (1,1,1) (3, 0) (2,1,1) (2, 0) (2, 2, 1) (3, 0) (3,1,1) (2, 0) (3, 2, 1) (1, 0) ,1,1 (4) (0, 0) (4, 2, 1) (0) (0, 2, 1) (4, 0) (1,1,1) (3, 0) (2,1,1) (2, 0) (2, 2, 1) (3, 0) (3,1,1) (2, 0) (3, 2, 1) (1, 0) (4, 2, 1) (0) (0, 2, 1) (4, 0) (1,1,1) (3, 0) (2,1,1) (2, 0) (2, 2, 1) (3, 0) (3,1,1) (2, 0) (3, 2, 1) (0, 2) (4, 2, 1)...Copy the code

The specific code is as follows:

/* First solve problem 1: in the simplest form, 3 merchants (m) and 3 attendants (F) cross the river and have a feasible state. The mode of state transfer from the initial state to the final state is m, the number of merchants on the left side of the river, f, the number of attendants, b=0, the ship on the left, 1 on the right */
#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 to the left, 1 to the right
   vector<int> sons;
};
vector<State> trackTree;
vector<int> trackStack;
int mNum, fNum, bCap;
int stateNum;
// Note: The state cannot be transferred back when the state is transferred, otherwise it may recurse indefinitely
// Set flags for passing states
// DFS returns 0 to indicate that there is no viable path, and positive to indicate the subscript of the node in the 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))
            {
               // Execute only once
               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(a)
{
   for (int m = 0; m <= mNum; m++)
   {
      for (int f = 0; f <= fNum; f++)
      {
         int m1 = mNum - m, f1 = fNum - f;
         // On either side, there are more merchants than minions or zero merchants is a viable state
         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)
   {
      // Now there is a complete track in the stack
      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(a);return;
   }
   for (auto son : trackTree[index].sons)
   {
      Print(son);
   }
   trackStack.pop_back(a);return;
}
int main(a)
{
   cout << "Please enter the number of merchants, number of attendants and vessel capacity respectively :\n";
   cin >> mNum >> fNum >> bCap;
   setEnableState(a); cout <<"Number of all states:" << stateNum << '\n';
   trackTree.push_back(State()); // Add an empty piece of data
   if (DFS(mNum, fNum, 0))
   {
      for (int i = 0; i < trackTree.size(a); i++)if (trackTree[i].b == 0 && trackTree[i].f == fNum && trackTree[i].m == mNum)
            Print(i);
   }
   else
      cout << "There is no solution! \n";
   return 0;
}
Copy the code