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

See previous articles:

Applying the algorithm to practice — Merchant crossing the River problem — Merchant crossing the River: How to use graph algorithm to find all the solutions? – the nuggets (juejin. Cn)

From one river to two

We further extend the problem of merchants crossing the river by turning one river into two.

The problem then becomes: MMM merchants and FFF entourage cross the river by boat. There are two rivers divided into three banks, and you can only cross the river if you reach the rightmost bank. There’s a boat on the shore right now just big enough for the BBBS, and they’re rowing by themselves. If there were more followers than merchants on either side of the river, they might rob. But it was the merchants who decided how to cross the river. How could the merchants safely cross the river with all their followers?

How do I represent states?

First set three banks as left bank (bank 0), middle bank (bank 1), right bank (bank 2);

If we still represent the state in the same way as the previous three variables (where BBB is 0, 1, 20, 1, 2, respectively, indicating that the ship is on the left bank, middle bank, and right bank) :


( 1 . 0 . 2 ) ,0,2 (1)

This state indicates that there is a merchant on the left bank, no follower, and the ship is on the right bank. But how do you determine how much of the rest is on the middle bank and how much is on the right bank?

So we can only extend the dimensions and use five variables to determine the unique state. It has the following definitions:


( m 1 . f 1 . m 2 . f 2 . b ) (m1,f1,m2,f2,b)

M1m1m1 merchants and F1F1F1 minions on the left bank, M2M2m2 merchants and F2F2F2 minions on the middle bank, the ship at BBB.

Then the number of people on the right bank can be easily deduced, thus representing the unique state.

The first four states can be used to represent the number of people in any two of the three banks, and the remaining one can be inferred.

Time complexity is too high!!

If you still use DFS today, the time complexity would be incredible. Because in the first section, my DFS was specially engineered to print all paths, but the time complexity is exponentially higher!

So we settle for one of the shortest possible paths.

At this time, the time complexity is greatly optimized: Dijkstra algorithm is used to make the complexity O(ElgV)O(ElgV)O(ElgV) when the number of vertices is VVV and the number of edges is EEE.

I also optimized the output of the program this time:

Please input the number of merchants, number of attendants and vessel capacity respectively: 5, 5, 2 have solutions, shortest degree: 34 Merchants river after the river | | businessman after | | businessman after -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 5 5 | | 0 0 | | 0 0 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 4 4 | | 1 -- 1 | | 0 0 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 4 4 | | 0 0 | | - 1 1 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 4 4 | | 1-0 | | 0 1 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 5-4 | | 0 0 | | 0 1 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 4 | 3 | 1 -- 1 | | 0 1 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -... -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 0 0 | | 0 2 | | 5 -- 3 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 0 0 | | 0-3 | | 5 2 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 0 0 | | 0 1 | | 5 -- 4 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 0 0 | | 1 -- 1 | | 4 4 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 0 0 | | 0 0 | | 5-5 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --Copy the code

The complete code

Given n bank variables: m1,f1,m2,f2,b, m1/f1 refers to the number of people on bank 1 m2/f2 refers to the number of people on bank 2 b is where the boat is parked The number of people on Bank 3 can be inferred so that a unique state can be expressed the transfer of state as usual */
#include <iostream>
#include <vector>
#include <queue>
#include <numeric>
#include <string.h>
using std::cin;
using std::cout;
using std::fill_n;
using std::priority_queue;
using std::string;
using std::vector;
const int maxn = 50;
const int inf = 0x3f3f3f3f;
struct node
{
   int m1;
   int f1;
   int m2;
   int f2;
   int b;
};
struct Dist
{
   int m1;
   int f1;
   int m2;
   int f2;
   int b;
   int dist;
   bool operator< (const Dist &a) const
   {
      returndist > a.dist; }};int found[maxn][maxn][maxn][maxn][3];
int able[maxn][maxn][maxn][maxn];
vector<node> graph[maxn][maxn][maxn][maxn][3];
int dist[maxn][maxn][maxn][maxn][3];
node last[maxn][maxn][maxn][maxn][3];
int mNum, fNum, bCap;
// Ensure that the status is valid
void AddEdge(int m1, int f1, int m2, int f2)
{
   int m3 = mNum - m1 - m2, f3 = fNum - f1 - f2;
   for (int b = 0; b <= 2; b++)
      for (int dm = 0; dm <= bCap; dm++)
         for (int df = 0; df + dm <= bCap; df++)
         {
            if (df + dm == 0)
               continue;
            int ml, fl, mr, fr, m1t, f1t, m2t, f2t, b1;
            if(b ! =0)
            {
               if (b == 1)
                  m1t = ml = m1 + dm,
                  f1t = fl = f1 + df,
                  m2t = mr = m2 - dm,
                  f2t = fr = f2 - df,
                  b1 = 0;
               else
                  m1t = m1,
                  f1t = f1,
                  m2t = ml = m2 + dm,
                  f2t = fl = f2 + df,
                  mr = m3 - dm,
                  fr = f3 - df,
                  b1 = 1;
               if (ml <= mNum && fl <= fNum && mr >= 0 && fr >= 0 && able[m1t][f1t][m2t][f2t])
                  graph[m1][f1][m2][f2][b].push_back(node{m1t, f1t, m2t, f2t, b1});
            }
            if(b ! =2)
            {
               if (b == 0)
                  m1t = ml = m1 - dm,
                  f1t = fl = f1 - df,
                  m2t = mr = m2 + dm,
                  f2t = fr = f2 + df,
                  b1 = 1;
               else if (b == 1)
                  m1t = m1,
                  f1t = f1,
                  m2t = ml = m2 - dm,
                  f2t = fl = f2 - df,
                  mr = m3 + dm,
                  fr = f3 + df,
                  b1 = 2;
               if (mr <= mNum && fr <= fNum && ml >= 0 && fl >= 0 && able[m1t][f1t][m2t][f2t])
                  graph[m1][f1][m2][f2][b].push_back(node{m1t, f1t, m2t, f2t, b1}); }}}void SetEnableState(a)
{
   for (int m1 = 0; m1 <= mNum; m1++)
      for (int f1 = 0; f1 <= fNum; f1++)
         for (int m2 = 0; m2 + m1 <= mNum; m2++)
            for (int f2 = 0; f2 + f1 <= fNum; f2++)
            {
               int m3 = mNum - m1 - m2, f3 = fNum - f1 - f2;
               // On either side, there are more merchants than minions or zero merchants is a viable state
               if ((m1 >= f1 || m1 == 0) && (m2 >= f2 || m2 == 0) && (m3 >= f3 || m3 == 0))
                  able[m1][f1][m2][f2] = 1; }}void SetGraph(a)
{
   for (int m1 = 0; m1 <= mNum; m1++)
      for (int f1 = 0; f1 <= fNum; f1++)
         for (int m2 = 0; m2 + m1 <= mNum; m2++)
            for (int f2 = 0; f2 + f1 <= fNum; f2++)
               if (able[m1][f1][m2][f2])
                  AddEdge(m1, f1, m2, f2);
}
void Dijkstra(a)
{
   priority_queue<Dist> q;
   memset(dist, inf, sizeof(dist));
   dist[mNum][fNum][0] [0] [0] = 0;
   q.push(Dist{mNum, fNum, 0.0.0.0});
   while(! q.empty())
   {
      auto tmp = q.top(a);int m1 = tmp.m1, f1 = tmp.f1, m2 = tmp.m2, f2 = tmp.f2, b = tmp.b, d = tmp.dist;
      q.pop(a); found[m1][f1][m2][f2][b] =1;
      for (auto v : graph[m1][f1][m2][f2][b])
      {
         int m1t = v.m1, f1t = v.f1, m2t = v.m2, f2t = v.f2, bt = v.b;
         if (d + 1 < dist[m1t][f1t][m2t][f2t][bt])
         {
            last[m1t][f1t][m2t][f2t][bt] = {m1, f1, m2, f2, b};
            dist[m1t][f1t][m2t][f2t][bt] = d + 1;
            q.push(Dist{m1t, f1t, m2t, f2t, bt, d + 1}); }}while(! q.empty())
      {
         auto tmp = q.top(a);int m1t = tmp.m1, f1t = tmp.f1, m2t = tmp.m2, f2t = tmp.f2, bt = tmp.b;
         if (found[m1t][f1t][m2t][f2t][bt])
            q.pop(a);else
            break; }}}void recur(int m1, int f1, int m2, int f2, int b)
{

   if (m1 == mNum && f1 == fNum && b == 0)
   {
      printf(" %d %d | | %d %d | | %d %d \n", m1, f1, m2, f2, mNum - m1 - m2, fNum - f1 - f2);
      printf("-------------------------------------\n");
      return;
   }
   node tmp = last[m1][f1][m2][f2][b];
   int m1t = tmp.m1, f1t = tmp.f1, m2t = tmp.m2, f2t = tmp.f2, bt = tmp.b;
   recur(m1t, f1t, m2t, f2t, bt);
   if (b == 0)
      printf(" %d -- %d | | %d %d | | %d %d \n", m1, f1, m2, f2, mNum - m1 - m2, fNum - f1 - f2);
   else if (b == 1)
      printf(" %d %d | | %d -- %d | | %d %d \n", m1, f1, m2, f2, mNum - m1 - m2, fNum - f1 - f2);
   else
      printf(" %d %d | | %d %d | | %d -- %d \n", m1, f1, m2, f2, mNum - m1 - m2, fNum - f1 - f2);
   printf("-------------------------------------\n");
   return;
}
int main(a)
{
   cout << "Please enter the number of merchants, number of attendants and vessel capacity respectively :\n";
   cin >> mNum >> fNum >> bCap;
   // Set the available state
   SetEnableState(a);/ / the edge
   SetGraph(a);Dijkstra(a);if (dist[0] [0] [0] [0] [2] != inf)
   {
      cout << "There are solutions, shortest degree:" << dist[0] [0] [0] [0] [2] < <"\n sequential state: \n";
      cout << "Merchants of follow | | river after the river | | businessman after \ n";
      cout << "-------------------------------------\n";
      recur(0.0.0.0.2);
   }
   else
      cout << "No solution!";
   return 0;
}
Copy the code