解題區/解題區 - UVa

UVa 250 - Pattern Matching Prelims

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

對於一個 N * M 的灰階矩陣，找一個重心$(c_{x}, c_{y})$，重心會符合將
$$|column[0, c_{x}-1] - column[c_{x}+1, N-1]| \\ |row[0, c_{y}-1] - row[c_{y}+1, M-1]|$$

最小化, 其中 column, row 表示該列、該行的總和。如果有數個相同，則盡可能輸出最右小角的座標 (座標值越大越好)

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
5 5
0.1 0.2 0.1 0.2 0.1
0.1 0.2 0.3 0.1 0.1
0.2 0.3 0.1 0.1 0.3
0.4 0.1 0.1 0.1 0.2
0.2 0.2 0.3 0.3 0.1
5 10
0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1
0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2
0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3
0.4 0.4 0.4 0.4 0.4 0.4 0.4 0.4 0.4 0.4
0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.6
0 0

Sample Output

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

Solution

其實會發現 x 軸、y 軸的結果可以分開計算，是不會影響最後的結果，兩別分別取最佳的位置即可。

而為了求這個值，累計每一行、列的總和，使用 O(n) 掃描計算即可。參照代碼。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <stdio.h>
#include <math.h>
int main() {
#define eps 1e-6
    int n, m, cases = 0;
    while(scanf("%d %d", &n, &m) == 2 && n+m) {
        double row[128] = {}, col[128] = {};
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                double x;
                scanf("%lf", &x);
                row[i] += x, col[j] += x;
            }
        }
        double left = 0, right = 0;
        double diff = 1e+30;
        int cx, cy;
        for(int i = 1; i < n; i++)
            right += row[i];
        for(int i = 0; i < n; i++) {
            if(fabs(right - left) < diff + eps) {
                diff = fabs(right - left);
                cx = i;
            }
            left += row[i], right -= row[i+1];
        }
        left = right = 0;
        diff = 1e+30;
        for(int i = 1; i < m; i++)
            right += col[i];
        for(int i = 0; i < m; i++) {
            if(fabs(right - left) < diff + eps) {
                diff = fabs(right - left);
                cy = i;
            }
            left += col[i], right -= col[i+1];
        }
        printf("Case %d: center at (%d, %d)\n", ++cases, cx+1, cy+1);
    }
    return 0;
}