41 - ACM ICPC Regional 2005, Hangzhou, Preliminary - 1005
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
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.
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.
2 2 24 91
3 3 144 194
2 4 111 19