Energy Minimization

Time limit: 1 Seconds

Memory limit: 32768K

Many of the problems that arise in early computer vision can be naturally expressed in terms of minimization of an energy function. Typically, researchers need to rely on general-purpose optimization techniques such as simulated annealing, which is extremely slow in practice. Some functions that have a restricted form can be solved efficiently using subtle algorithms. In this problem your task is to write a program to find the minimal value of a special class of energy functions widely used in image processing.

Suppose an image has R rows and C columns. We can assign each of the pixel a number ranging from 1 to R * C depending on its scan-line order. We define n = R * C and the energy function is in the form of

where

• j in N(i) means that the pixel j is in the left, right, top or bottom neighbor of pixel i;

• the integer pi (0 <= pi <= 255) is the gray level of the pixel i;

• xi (xi in {0, 1}) is the assigned label to the pixel i; and

• the integers v0 and v1 (0 <= v0, v1 <= 255) are the prior estimation of the gray level of the pixels labeled 0 and 1 respectively.

1. Input

Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 10) which is the number of test cases. T test cases follow, each preceded by a single blank line.

The first line of each test case contains four integers R, C (2 <= R, C <= 20), v0 and v1. The following R lines contain C integers each, which are the gray level of the pixels. The proper ranges are shown in the problem description.

2. Output

Results should be directed to standard output. Start each case with "Case #:" on a single line, where # is the case number starting from 1. Two consecutive cases should be separated by a single blank line. No blank line should be produced after the last test case.

For each case, output the minimized energy value in a single line.

3. Sample Input

3

2 2 24 91
236 224
250 248

3 3 144 194
44 33 24
92 4 227
47 63 35

2 4 111 19
65 86 109 153
115 186 146 112

4. Sample Output

Case 1:
594

Case 2:
893

Case 3:
230