首页 > ACM题库 > HDU-杭电 > hdu 2420 Cube and Caterpillar待解决[解题报告]C++
2014
01-26

hdu 2420 Cube and Caterpillar待解决[解题报告]C++

Cube and Caterpillar

问题描述 :

Consider a cube of size 3 * 3 * 3. Let us number the 27 blocks in it as follows:
1 2 3
4 5 6
7 8 9

10 11 12
13 14 15
16 17 18

19 20 21
22 23 24
25 26 27
(The top layer is given first, followed by the middle, then the bottom one)

It is known that a strange caterpillar is stuck inside this cube. The length of its body is exactly 27, thus there is exactly one section of its body in each cell of the cube. The caterpillar’s body is not necessarily straight; it may turn in any of the six directions (provided that the cell adjacent in that direction exists). You’re given the information of which parts of the caterpillar’s body turned in the respective cells, please find whether such a solution exists; if it does, output the lexicographically smallest one.

输入:

The first line of the input contains one integer, T, the number of test cases. T lines follow, each line containing 25 integers, describing the statuses of all parts of the caterpillar’s body except head and tail, in the order from head to tail; if the ith integer is non-zero, it means that the caterpillar’s (i+1)th part of body turned in its cell.

输出:

The first line of the input contains one integer, T, the number of test cases. T lines follow, each line containing 25 integers, describing the statuses of all parts of the caterpillar’s body except head and tail, in the order from head to tail; if the ith integer is non-zero, it means that the caterpillar’s (i+1)th part of body turned in its cell.

样例输入:

2
0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

样例输出:

Case 1:
1 2 3
6 5 4
7 8 9

18 13 12
17 14 11
16 15 10

19 20 21
24 23 22
25 26 27


Case 2:
No solution


  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  2. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  3. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  4. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?