2014
01-26

# 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;