积木搭建解题报告

[问题描述]

单位立方体(unit cube)是一个1×1×1的立方体，它的所有角的x,y和z坐标都是整数。我们称两个单位立方体是连通的，当且仅当他们有一个公共的面；一个构形(solid)或者是一个单位立方体，或者是由多个单位立方体组成的连通物体(如图一所示)，它的体积就是它所含的单位立方体的个数。

一块积木(block)是一个体积不超过4的构形。如果两块积木可以平移、旋转(注意，不能成镜像)操作变得完全一样，我们就称它们属于同一类。这样，积木总共有12类(如图2所示)。图2中积木的不同颜色仅仅是为了帮助你看清楚它的结构，并没有其他的含义。

一个构形可以由若干块积木组成。如果用一些积木可以互不重叠的搭建出某个构形，那么就称这些积木是这个构形的一种分解(decomposition)。

你的任务是写一个程序,对于给定的一组积木种类和一个构形S,求出境可能少的积木个数,使得他们能够搭建出构形S。你只需给出这个最少的积木个数，以及这些积木各自所属的种类，而不必给出具体的搭建方案。

[输入输出格式]

(1)输入：

在输入文件中，一个单位立方体用同一行中的三个整数x,y,z表示。坐标(x,y,z)是该单位立方体各个顶点坐标{(x_i,y_i,z_i)|i=1..8}中x_i+y_i+z_i最小的。

输入文件有两个。第一个输入文件描述了积木的不同种类，文件为types.in。在下问“输入输出样例”部分给出了一个types.in文件,他一次定义了图2所示的12中积木。注意：所有的测试数据都将统一采用该types.in文件。

每一种类的积木由连续的若干行描述。第一行市积木的种类编号I(1≤I≤12)；第二行是该类积木的体积V(1≤V≤4)；随后的V行每行包含三个整数x,y和z，表示组成该类积木的一个单位立方体，其中1≤x,y,z≤4。

(2)输出：

输出的文件名为：block.out。

它的第一行是一个正整数M，表示使用积木的最少块数。

文件的第二行列出M个整数，表示搭建出构形S的M块积木各自的种类。

[输入输出样例]

block.in 18 2 1 1 4 1 1 2 3 1 4 3 1 2 1 2 3 1 2 4 1 2 1 2 2 2 2 2 3 2 2 4 2 2 2 3 2 3 3 2 4 3 2 4 2 3 4 2 4 4 2 5 5 2 5

types.in 1 1 1 1 1 2 2 1 1 1 1 2 1 3 3 1 1 1 1 2 1 1 3 1 4 3 1 1 1 1 2 1 1 1 2 5 4 1 1 1 1 2 1 1 3 1 1 4 1

6 4 1 1 1 1 2 1 1 1 2 1 2 2 7 4 1 1 1 1 2 1 1 1 2 1 1 3 8 4 1 1 1 1 2 1 1 3 1 1 2 2 9 4 1 2 1 1 3 1 1 1 2 1 2 2

10 4 2 1 1 1 2 1 2 2 1 2 1 2 11 4 1 1 1 1 2 1 2 2 1 1 1 2 12 4 2 2 1 2 1 2 1 2 2 2 2 2

block.out 5 7 10 2 10 12

[数据结构]

为描述清楚，先列出数据结构：

TPoint = record  {空间中的一个单位立方体}

  x,y,z: Shortint;

end;

Tar： array[1..50] of TPoint; {目标形状}

TCube = array[1..4] of TPoint; {一个积木}

Cube: array[1..most] of TCube; {所有的状态}

[算法分析]

看到这个题目，就会想到搜索。这是一道有一定难度的题目，盲目的搜索是不行的，因为题目中说明了每种积木都可以经过翻转和平移，然而，只要得到了平移或翻转后的积木，我们就只需要一个一个的往构形里面填，直到填满，这显然是一个深度优先搜索。然而对于这道题目来说，除了搜索之外，还有一个难点，就是生成所有的翻转或平移后的积木状态。

我们考虑用一个三员组表示空间中的1*1*1的立方体(单位立方体)，三员组(x,y,z)表示空间(x,y,z)处有一个单位立方体。这样我们就有三种数据结构：

TPoint = record{一个点}

y

z

x

    x,y,z: Shortint;

end；

TCube = array[1..4] of TPoint;{一个积木}

TBlock = array[1..50] of TPoint;{给定的三维形状}

右图所示图形可表示为：

(0,0,0) (0,0,1) (0,1,1)

怎样生成所有状态：

首先，题目中指出：可以平移，翻转，但不可以成镜像。如何处理平移？我们只要保存一个积木中四个顶点的相对位置，在搜索的时候自然就可以完成平移，在此我们规定一个积木的一个单位立方体为(0,0,0)，则其余三个可以用相对于这个单位立方体的位置来表示。如何处理翻转？由于题目规定不可以成镜像，所以，我们在生成所有状态时的翻转过程中，必成偶数次镜像(因为：成偶数次镜像等于没成镜像)。由于旋转积木很难理解，也有可能会遗漏一些情况，我们采用的是旋转坐标轴的方法。

可以这么理解旋转坐标轴法：

顾名思义，就是要在三维空间中，将坐标轴旋转，当然，旋转后的坐标要两两垂直，在满足这个条件的情况下，用temp:TCube表示某积木cube Tcube经过某种旋转后所得的状态。设func(temp)表示有几条坐标线(射线)所在直线和原来这条坐标线所在直线的不重合的。考虑func(temp)的不同值：设f(temp)表示在func(temp)的基础上得到的表示temp性质的函数:

f(temp)

0                           (func(temp) = 0) or (func(temp) = 3)        {旋转时没有成镜像}

1          (func(temp) = 2)        {旋转时成了镜像}

注:func(temp)=1是不可能的。

对于某一条特定的坐标，如果规定一个方向为正方向，则可以用g(temp)表示旋转后的新坐标线中方向和原来方向不同的条数。(注：这里的方向并非表示三维空间中的方向，只表示正负)。易得：若f(temp)+g(temp)为偶数，则temp是符合题意，即成偶数次镜像的。

搜索的时候，另需一个数组space:array[1..7,1..7,1..7] of byte;

space[x,y,z]=1表示此处未放, space[x,y,z]=0表示放了。

procedure search(u,dep,left: integer);

var

  i: integer;

begin

  if left = 0 then

  begin

    修改;退出;

  end;

  若(left – 1) DIV 4 + 1 >= min then Exit;{分支定界}

  找到一个space [tar[u,1],tar[u,2],tar[u,3]]<>0的u;{tar是目标形状}

  若不存在则退出;

  repeat

    找到一个可以放置且覆盖(tar[u,1],tar[u,2],tar[u,3])的积木;

    若找到则:

    begin

      放下;

      search(u+1,dep+1,left-count[i]);{count[i]是第I个积木的体积}

    end;

  until 找不到;

end;

值得注意的是, 找一个可放置的积木时,我们不仅要枚举积木，而且要枚举点(tar[u,1],tar[u,2],tar[u,3])在积木中的位置。如下面的图形:我们要枚举点(tar[u,1],tar[u,2],tar[u,3])在积木中的四中位置情况,然后递归搜索，这样才能够全面。

至此，这道题目可以说是得到比较圆满解决了，按照这种方法便出来的程序速度是比较快的，能够对一半左右的测试数据。

[优化方法]

这里讲的优化，主要是针对搜索时的一些技巧来讲的。

在搜索的过程中，我们发现：我们的目的实际上就是要把一些积木放到构形里面去，不妨换个角度，把一个构形看成由许多单位立方体构成的，同样的，一个积木也是由许多单位立方体构成。我们把这个构形拆开承单个的单位立方体，每次从里面去出成分和某一块积木陈分相同一些单位立方体。因此，不妨令这些单位立方体是有序的，同样，积木的描述也是有序的。搜索时，由小到大去填充构形的某一个单位立方体，如果轮到填充构形中的某一个单位立方体时，我们就必须让它成为某一个积木描述中最靠前(最”小”)的那一部分，因为如果不这样，这个单位立方体就再不可能被覆盖了。这样就免去了上面所说的确定这个单位立方体中相对位置的过程，效率有很大的提高。然而，我们需要一个标准来衡量一个单位立方体的“大小”，这很简单，就先以x为关键字排序；在x相同的前提下，以y为关键字排序；在x,y都相同的前提下，以z为关键字排序。

在程序开始时可以得到一个最优值best=(n – 1) DIV 4 + 1;一旦搜索到的解达到了这个值就可以中止程序。

因为各种积木的第一个单位立方体都是(0,0,0)，保存各种状态时只需用三个TPoint，虽然这对于空间存储来说并不是问题。

此外,搜索的顺序对于时间效率很重要，在编程当中，我发现，若把较为平直的积木放在cube数组的前面，这样，循环时先找到的就是较平直的，事实证明，用这样的方法，很多的数据都有明显的超时，这可能是由于平直的积木不利于剪枝而造成的。我们可以同样考虑将积木按体积从达到小排序，这样，即容易出解也利于剪枝。

搜索序列 示例的出解时间 平直积木优先顺序 0.48s 随机积木顺序 0.15s types.in中的顺序 0.08s 体积大的优先顺序 <0.01s

如下表，给出了示例数据的出解时间：

 

 

 

 

[时空复杂度]

空间上：有用状态数不是很多，105种，而且目标形状的体积也不是很大，所以空间上是完全承受的了的。

 

时间上：由于有很多的状态是不能被放置的，所以有了上面的分支定界和剪枝，应该可以在规定时间内出解。

[总结]

做这类题目时应该仔细分析清楚题目，抓住主要矛盾，对这道题来讲就是要仔细分析生成所有状态的方法。

[程序]

预处理程序:

program Preparation;

const

  inputfile = 'types.in';

  outputfile = 'kind.out';

  Dir: array[1..6, 1..3] of Shortint = {使坐标轴之间产生互换的数组}

((1,3,2),(3,2,1),(2,1,3),(1,2,3),(2,3,1),(3,1,2));

  Sign: array[1..8, 1..3] of Shortint = {使坐标轴产生方向变化的数组}

((-1, 1, 1),( 1,-1, 1),( 1, 1,-1),(-1,-1,-1),

 ( 1, 1, 1),(-1,-1, 1),(-1, 1,-1),( 1,-1,-1));

type

  TPoint = array[1..3] of Shortint; {一个单位立方体}

  TCube = record {一个积木}

    Count: Byte; {体积}

    Struct: array[1..4] of TPoint; {结构}

  end;

var

  Cube, Temp: TCube;

  Cubes: array[1..300] of TCube; {保存所有的积木}

  Source: array[1..300] of Byte; {这种积木是有第几总积木旋转而来}

  CubeCount, I, J, K, P, Q, N, V, mX, mY, mZ: Integer;

  head, tail: integer;

function App: Boolean; {判断一种积木是否是重复的}

var

  I, J, P, dX, dY, dZ: Integer;

  E: TPoint;

  Same: Boolean;

begin

  App := True;

  with Temp do

  begin

    for i := 1 to Count - 1 do {排序}

    begin

      P := i;

      for j := i to Count do

        if (Struct[j, 1] < Struct[P, 1]) or

           (Struct[j, 1] = Struct[P, 1]) and (Struct[j, 2] < Struct[P, 2]) or

           (Struct[j, 1] = Struct[P, 1]) and (Struct[j, 2] = Struct[P, 2]) and

           (Struct[j, 3] < Struct[P, 3]) then P := j;

      E := Struct[i];

      Struct[i] := Struct[P];

      Struct[P] := E;

    end;

    for i := 1 to CubeCount do {判断重复情况}

      if Cubes[i].Count = Count then

      begin

        dX := Cubes[i].Struct[1, 1] - Struct[1, 1];

        dY := Cubes[i].Struct[1, 2] - Struct[1, 2];

        dZ := Cubes[i].Struct[1, 3] - Struct[1, 3];

        Same := True;

        for j := 1 to Count do

          if (Cubes[i].Struct[j, 1] - Struct[j, 1] <> dX) or

             (Cubes[i].Struct[j, 2] - Struct[j, 2] <> dY) or

             (Cubes[i].Struct[j, 3] - Struct[j, 3] <> dZ) then

          begin

            Same := False;

            Break;

          end;

        if Same then Exit;

      end;

  end;

  App := False;

end;

begin

  Assign(input, inputfile); Reset(input);

  for i := 1 to 12 do {读入}

  begin

    Readln(N);

    Readln(V);

    Cube.Count := 0;

    for j := 1 to V do

      with Cube do

      begin

        Inc(Count);

        Readln(Struct[Count, 1], Struct[Count, 2], Struct[Count, 3]);

      end;

    for j := V downto 1 do {转化为相对坐标}

      with Cube do

      begin

        Dec(Struct[j, 1], Struct[1, 1]);

        Dec(Struct[j, 2], Struct[1, 2]);

        Dec(Struct[j, 3], Struct[1, 3]);

      end;

    Temp.Count := V;

    for k := 1 to 6 do

    begin

      if k <= 3 then {分情况旋转坐标}

      begin

        head := 1; tail := 4;

      end

      else

      begin

        head := 5; tail := 8;

      end;

      for q := head to tail do

      begin

        for j := 1 to V do

          with Temp do

            for p := 1 to 3 do

              Struct[j, p] := Cube.Struct[j, Dir[k, p]] * Sign[q, p];

        if not App then {增加一种新的积木}

        begin

          Inc(CubeCount);

          Cubes[CubeCount] := Temp;

          Source[CubeCount] := N;

        end;

      end;

    end;

  end;

  Close(input);

  Assign(output, outputfile); Rewrite(output);

  Writeln(CubeCount); {具体输出过程略}

  Close(output);

end.

解题程序:

{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S-,T-,V+,X+,Y+}

{$M 16384,0,655360}

program BLOCK;

const

  inputfile = 'block.in';

  checkfile = 'block.ans';

  outputfile = 'block.out';

  Most = 105;

type

  TPoint = array[1..3] of Integer;

  TCube = array[1..3] of TPoint;

const

  Source: array[1..Most] of Byte = (5,5,5,6,6,6,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,9,9,9,10,10,10,10,10,10,10,10,10,10,10,10,11,11,11,11,11,11,11,11,11,11,11,11,12,12,12,12,12,12,12,12,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,2,2,2,1);

  Count: array[1..Most] of Byte = (4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,2,2,2,1);

  Cube: array[1..Most] of TCube = (((0,0,1),(0,0,2),(0,0,3)),((0,1,0),(0,2,0),(0,3,0)),((1,0,0),(2,0,0),(3,0,0)),

 ((0,0,1),(0,1,0),(0,1,1)),((0,1,0),(1,0,0),(1,1,0)),((0,0,1),(1,0,0),(1,0,1)),

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

 ((0,1,0),(0,2,-1),(0,2,0)),((1,0,0),(2,0,0),(2,1,0)),((0,1,0),(1,1,0),(2,1,0)),

 ((0,1,0),(1,0,0),(2,0,0)),((1,0,0),(2,-1,0),(2,0,0)),((1,0,0),(1,0,1),(1,0,2)),

 ((0,0,1),(0,0,2),(1,0,0)),((0,0,1),(0,0,2),(1,0,2)),((1,0,-2),(1,0,-1),(1,0,0)),

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

 ((0,1,-2),(0,1,-1),(0,1,0)),((0,1,0),(0,2,0),(1,0,0)),((1,-2,0),(1,-1,0),(1,0,0)),

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

 ((1,0,0),(2,0,0),(2,0,1)),((1,0,0),(2,0,-1),(2,0,0)),((0,0,1),(1,0,1),(2,0,1)),

 ((0,0,1),(0,0,2),(0,1,1)),((0,1,-1),(0,1,0),(0,1,1)),((1,-1,0),(1,0,0),(1,1,0)),

 ((0,1,0),(0,2,0),(1,1,0)),((1,0,0),(1,0,1),(2,0,0)),((1,0,-1),(1,0,0),(2,0,0)),

 ((0,1,0),(0,1,1),(0,2,0)),((0,1,-1),(0,1,0),(0,2,0)),((1,0,0),(1,1,0),(2,0,0)),

 ((1,-1,0),(1,0,0),(2,0,0)),((0,0,1),(0,0,2),(1,0,1)),((1,0,-1),(1,0,0),(1,0,1)),

 ((0,0,1),(0,1,-1),(0,1,0)),((0,0,1),(0,1,1),(0,1,2)),((0,1,0),(1,1,0),(1,2,0)),

 ((0,1,0),(1,-1,0),(1,0,0)),((1,0,0),(1,0,1),(2,0,1)),((1,0,-1),(1,0,0),(2,0,-1)),

 ((0,1,-1),(0,1,0),(0,2,-1)),((0,1,0),(0,1,1),(0,2,1)),((1,-1,0),(1,0,0),(2,-1,0)),

 ((1,0,0),(1,1,0),(2,1,0)),((0,0,1),(1,0,-1),(1,0,0)),((0,0,1),(1,0,1),(1,0,2)),

 ((0,0,1),(0,1,0),(1,0,1)),((1,-1,-1),(1,0,-1),(1,0,0)),((1,0,0),(1,0,1),(1,1,1)),

 ((0,1,-1),(0,1,0),(1,1,-1)),((1,0,0),(1,1,-1),(1,1,0)),((0,0,1),(0,1,1),(1,1,1)),

 ((0,1,0),(0,1,1),(1,0,0)),((1,-1,0),(1,-1,1),(1,0,0)),((0,1,0),(1,1,0),(1,1,1)),

 ((0,0,1),(1,0,0),(1,1,0)),((0,0,1),(1,-1,1),(1,0,1)),((0,1,0),(1,0,-1),(1,0,0)),

 ((1,0,-1),(1,0,0),(1,1,-1)),((0,1,0),(0,1,1),(1,1,1)),((0,0,1),(0,1,1),(1,0,0)),

 ((1,-1,1),(1,0,0),(1,0,1)),((1,0,0),(1,1,0),(1,1,1)),((0,0,1),(0,1,0),(1,1,0)),

 ((0,1,-1),(0,1,0),(1,0,0)),((1,-1,-1),(1,-1,0),(1,0,0)),((0,1,0),(1,0,0),(1,0,1)),

 ((0,0,1),(1,-1,0),(1,0,0)),((0,0,1),(1,0,1),(1,1,1)),((0,1,0),(1,1,-1),(1,1,0)),

 ((0,1,-1),(0,1,0),(1,1,0)),((1,0,-1),(1,0,0),(1,1,0)),((1,-1,0),(1,0,0),(1,0,1)),

 ((0,0,1),(0,1,0),(1,0,0)),((1,-1,0),(1,0,-1),(1,0,0)),((0,0,1),(0,1,1),(1,0,1)),

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

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

 ((0,1,0),(0,1,1),(0,0,0)),((0,0,1),(0,1,1),(0,0,0)),((0,1,-1),(0,1,0),(0,0,0)),

 ((1,0,0),(1,1,0),(0,0,0)),((0,1,0),(1,1,0),(0,0,0)),((0,1,0),(1,0,0),(0,0,0)),

 ((1,-1,0),(1,0,0),(0,0,0)),((1,0,0),(1,0,1),(0,0,0)),((0,0,1),(1,0,0),(0,0,0)),

 ((0,0,1),(1,0,1),(0,0,0)),((1,0,-1),(1,0,0),(0,0,0)),((0,0,1),(0,0,0),(0,0,0)),

 ((0,1,0),(0,0,0),(0,0,0)),((1,0,0),(0,0,0),(0,0,0)),((0,0,0),(0,0,0),(0,0,0)));

var

  F: array[-3..10, -3..10, -3..10] of Byte; {空间中的某一单位立方体是否被覆盖}

  Tar: array[1..50] of TPoint; {目标构形}

  Ans, Use: array[1..50] of Integer; {纪录所用的积木种类}

  N, Left, Min, OK: Integer;

  E, Ex: TPoint;

procedure Initalize; {读入,初始化}

var

  I: Integer;

begin

  Assign(input, inputfile); Reset(input);

  Readln(N);

  for i := 1 to N do

  begin

    Readln(Tar[i, 1], Tar[i, 2], Tar[i, 3]);

    F[Tar[i, 1], Tar[i, 2], Tar[i, 3]] := 1;

  end;

  Close(input);

  Min := N + 1; {现在的最优解,及全部用v=1的单位立方体构成需要N个,但为保证有解,就设置为N+1}

  OK := (N - 1) DIV 4 + 1; {极限最优解}

end;

procedure Sort(H, T: Integer); {快速排序}

var

  K1, K2 : Integer;

begin

  K1 := H; K2 := T;

  E := Tar[(H + T) DIV 2];

  while K1 <= K2 do

  begin

    while (Tar[K1, 1] < E[1]) or

          (Tar[K1, 1] = E[1]) and (Tar[K1, 2] < E[2]) or

          (Tar[K1, 1] = E[1]) and (Tar[K1, 2] = E[2]) and (Tar[K1, 3] < E[3]) do

      Inc(K1);

    while (Tar[ K2 , 1] > E[1]) or

          (Tar[K2, 1] = E[1]) and (Tar[ K2 , 2] > E[2]) or

          (Tar[K2, 1] = E[1]) and (Tar[K2, 2] = E[2]) and (Tar[ K2 , 3] > E[3]) do

      Dec( K2 );

    if K1 <= K2 then

    begin

      Ex := Tar[K1]; Tar[K1] := Tar[K2]; Tar[ K2 ] := Ex;

      Inc(K1); Dec( K2 );

    end;

  end;

  if H < K2 then Sort(H, K2 );

  if K1 < T then Sort(K1, T);

end;

procedure Search(U{现在填第几个单位立方体},

                                Dep{用了几个积木},

                                Left{还剩几个单位立方体未翻转}: Byte);

var

  I, x, y, z: Integer;

begin

  if Left = 0 then {已经填完了}

  begin

    if Dep < Min then {修改最优解}

    begin

      Min := Dep; Ans := Use;

    end;

    Exit;

  end;

  while (U <= N) and (F[Tar[U, 1], Tar[U, 2], Tar[U, 3]] = 0) do Inc(U);

 {找到一个未被覆盖的单位立方体}

  if U > N then Exit; {若不存在则退出}

  x := Tar[U, 1]; y := Tar[U, 2]; z := Tar[U, 3];

  for i := 1 to Most do

    if (Count[i] <= Left) and (F[x, y, z] = 1) and

       (F[x + Cube[i, 1, 1], y + Cube[i, 1, 2], z + Cube[i, 1, 3]] = 1) and

       (F[x + Cube[i, 2, 1], y + Cube[i, 2, 2], z + Cube[i, 2, 3]] = 1) and

       (F[x + Cube[i, 3, 1], y + Cube[i, 3, 2], z + Cube[i, 3, 3]] = 1) and

       (Left - Count[i] + 3 < (Min – Dep – 1) * 4) then {是否可以用它填充}

    begin

      Inc(Use[Source[i]]); {记录下这个积木的编号}

      F[x, y, z] := 0;

      F[x + Cube[i, 1, 1], y + Cube[i, 1, 2], z + Cube[i, 1, 3]] := 0;

      F[x + Cube[i, 2, 1], y + Cube[i, 2, 2], z + Cube[i, 2, 3]] := 0;

      F[x + Cube[i, 3, 1], y + Cube[i, 3, 2], z + Cube[i, 3, 3]] := 0; {填充}

      Search(U + 1, Dep + 1, Left - Count[i]);

      F[x, y, z] := 1;

      F[x + Cube[i, 1, 1], y + Cube[i, 1, 2], z + Cube[i, 1, 3]] := 1;

      F[x + Cube[i, 2, 1], y + Cube[i, 2, 2], z + Cube[i, 2, 3]] := 1;

      F[x + Cube[i, 3, 1], y + Cube[i, 3, 2], z + Cube[i, 3, 3]] := 1; {恢复填充}

      Dec(Use[Source[i]]); {删除这个积木的编号}

    end;

end;

procedure Print; {打印输出解}

var

  I, J: Integer;

begin

  Assign(output, outputfile); Rewrite(output);

  Writeln(Min);

  for i := 1 to 12 do

    for j := 1 to Ans[i] do

      Write(i, ' ');

  Close(output);

end;

begin

  Initalize;

  Sort(1, N);

  Search(1, 0, N);

  Print;

end.