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)).

For each test case, output the energy value of the Min-Surface-Carving as format shown at sample output.

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

hh314

2010 ACM-ICPC Multi-University Training Contest（14）——Host by BJTU