c++ - 算法-使最高的塔

我有一个无法解决的问题。我想过很多解决方案，但似乎没人能解决。

这就是我的问题：

您会得到n1，n2，.... nk个乐高积木，每个积木都有偶数个面孔。
只有在以下情况下，每个乐高积木才能堆叠在一起：


上层乐高与下层乐高具有相同的外观；
上部乐高的面部数量必须小于或等于其下方的乐高的面部数量。


除此之外，每个面都有一个相反的面，该面通过输入在第一个面之后插入；
例如：LEGO1-face1，face2，face3，face4（face1和face2是相反的，例如face3和face4）。

问题要求使用每个乐高积木仅用这些乐高积木建造最高的塔。
塔必须只有1个方向，因此只能从左到右或从下到上移动。

非常感谢，对不起我的英语不好：/

输入示例：

乐高1-f1，f2，f3，f4，f5，f6

乐高2- f33，f47，f98，f123

乐高3-F4，F127

输出示例：

2

最佳答案

类似于我很久以前的任务。该算法的思想是：


将项目（乐高）放入循环列表（封闭式单链列表）中；
使功能

循环中

从列表中获取下一个元素（将其删除）
递归校准自己
插入先前删除的元素
前进到下一个元素




当列表为空时，您可能获得了一种乐高序列。算法仅使用每个列表元素构建一次所有可能的默认情况。

工作代码：

#include <stdio.h>

#define MAX 4

struct CList{
   int d;
   struct CList *next;
};

void search(struct CList *pstart);
void result(struct CList *v[MAX], const int nv);

int main(){
   static struct CList lst[MAX];
   struct CList *p = lst;
   int i;
   for( i = 0; i < MAX - 1; i++){
      lst[i].d = i;
      lst[i].next = lst + i + 1;
   }
   lst[MAX-1].d = MAX - 1;
   lst[MAX-1].next = lst;
   search( p );
   return 0;
}

void search(struct CList *pstart){
   struct CList *p, *pp;
   static struct CList *v[MAX];
   static int nv = 0;
   if( pstart->next == pstart ){
      v[nv++] = pstart;
      result( v, nv );
      nv--;
      return;
   }
   nv++;
   p = pstart;
   do{
      pp = p;
      p = p->next;
      v[nv-1] = p;
      pp->next = p->next;
      search( pp );
      p->next = pp->next;
      pp->next = p;
   } while( p != pstart );
   nv--;
}

void result(struct CList *v[MAX], const int nv){
   int i;
   for( i = 0; i < nv; i++ ){
      printf(" %d ", v[i]->d);
   }
   puts( "" );
}

在您的情况下，可能可以进行进一步的优化（例如，当当前元素不堆叠时中断递归）。