ICPC 1996 · Problem F · Pattern Matching Prelims

Input file: pattern.in

Some algorithms for optical character recognition compare a scanned image with templates of “perfect” characters. Part of the difficulty with such comparisons is deciding where to start the comparison. This is because the characters in the scanned image are subject to noise and distortion, resulting in changes in size, position, and orientation. A procedure that is sometimes used to deal with changes in position matches the “center of gravity” of the scanned character and the templates against which it is compared. In this problem you are to determine the “centers of gravity” of scanned images of characters.

For our purposes, a scanned image will be a rectangular array of real numbers, each of which represents the gray- scale value of a point in a scanned image. Each gray-scale value will be between 0 (representing a totally white region) and 1 (representing a totally black region). The array will have no more than a total of 40 rows and columns.

The center of gravity will always correspond to a particular element in the array. If the center of gravity is the element in the ith row and jth column, for example, then we can say that the sum (or “weight”) of the elements in two portions of the array left after deleting the ith row would be equal to each other. Likewise, the sum of the elements in the two array portions formed by deleting the jth column would be equal. Consider the array shown below, which might have resulted from scanning a lower case “o.” The center of gravity for this array is uniquely in row 3, column 3. The sum of the elements in each array portion formed by deleting the third row is 5.65; the sum of each array portion formed by deleting the third column is 5.60.

.7 .75 .8 .75 .8 .55 .3 .2 .1 .7 .8 .1 .0 .0 .8 .7 .0 .0 .0 .8 .8 .9 .8 .75 .9

In most cases, however, the center cannot be placed as precisely as this. Thus the rule is that the center of gravity is to be placed so as to minimize the difference between the sums of the two portions of the array formed by deleting the row of the center of gravity and similarly for the portions formed by deleting the column of the center of gravity.

Input

The input will consist of a sequence of scanned character images. Input for each image will begin with two integers specifying the number of rows and columns in the scanned data. This will be immediately followed by the scanned gray-scale data given in row-major order. A pair of zeroes will follow the data for the last input image.

Output

For each input character image, display its number (they are sequentially numbered starting with 1), and the row and column corresponding to the center of gravity. If there are more than one center of gravity, the one with the largest row and column should be displayed. The sample that follows illustrates a reasonable output format.

Sample Input

5 5
.1 .2 .1 .2 .1
.1 .2 .3 .1 .1
.2 .3 .1 .1 .3
.4 .1 .1 .1 .2
.2 .2 .3 .3 .1
5 10
.1 .1 .1 .1 .1 .1 .1 .1 .1 .1
.2 .2 .2 .2 .2 .2 .2 .2 .2 .2
.3 .3 .3 .3 .3 .3 .3 .3 .3 .3
.4 .4 .4 .4 .4 .4 .4 .4 .4 .4
.5 .5 .5 .5 .5 .5 .5 .5 .5 .6
0 0

Output for the Sample Input

Case 1: center at (3, 3)
Case 2: center at (4, 6)