2014
11-27

# Cube Min Surface Carving

Given a cube with size x*y*z. each vertex has a non-negative weight w(x, y, z). As shown in figure 1, a surface-carving is a curved section on the XOY plane, and it has two properties:

Figure 1. The cube and the surface-carving example

1. Surface F is formed of x*y vertices, and there is one and only one vertex in each Z axis belonging to the surface.
2. For each vertex (x, y, z) on the surface，its XOY plane adjacent vertices(x+1, y, z’) or (x-1, y, z’) or (x, y+1, z’) or (x, y-1, z’) satisfy that |z- z’|<=1.
Define the energy of the surface F as the sum of the vertices value on it.
Please obtain the minimum value of the surface energy.

There are multiple test cases. first line input the number of the test case. The number of cases is less than 20.
For each test case, the first line contains three integers x, y and z(1<=x, y, z<=10), denoting the size of the cube.
The next x*y*z integers, denoting the weight of each vertex(x, y, z), ordered by the axis X, Y, Z. (eg. w(0,0,0), w(1,0,0), … w(0, 1, 0), … w(0, 0, 1)…w(x,y,z)).

There are multiple test cases. first line input the number of the test case. The number of cases is less than 20.
For each test case, the first line contains three integers x, y and z(1<=x, y, z<=10), denoting the size of the cube.
The next x*y*z integers, denoting the weight of each vertex(x, y, z), ordered by the axis X, Y, Z. (eg. w(0,0,0), w(1,0,0), … w(0, 1, 0), … w(0, 0, 1)…w(x,y,z)).

2

2 2 2
0 5
6 3
4 1
2 7

2 1 5
4 1
4 2
2 3
4 4
4 5

Case 1: 6
Case 2: 4

1. 你也说了是明面上，暗面里实质上转没转，败没败，大家都心知肚明。只不过你的队伍可以肆无忌惮地发言，大多数明白人却没法随心所欲地表达而已

2. 你也说了是明面上，暗面里实质上转没转，败没败，大家都心知肚明。只不过你的队伍可以肆无忌惮地发言，大多数明白人却没法随心所欲地表达而已

3. 你也说了是明面上，暗面里实质上转没转，败没败，大家都心知肚明。只不过你的队伍可以肆无忌惮地发言，大多数明白人却没法随心所欲地表达而已

4. 你也说了是明面上，暗面里实质上转没转，败没败，大家都心知肚明。只不过你的队伍可以肆无忌惮地发言，大多数明白人却没法随心所欲地表达而已

5. 你也说了是明面上，暗面里实质上转没转，败没败，大家都心知肚明。只不过你的队伍可以肆无忌惮地发言，大多数明白人却没法随心所欲地表达而已

6. 你也说了是明面上，暗面里实质上转没转，败没败，大家都心知肚明。只不过你的队伍可以肆无忌惮地发言，大多数明白人却没法随心所欲地表达而已

7. 你也说了是明面上，暗面里实质上转没转，败没败，大家都心知肚明。只不过你的队伍可以肆无忌惮地发言，大多数明白人却没法随心所欲地表达而已

8. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮