解題區/解題區 - UVa

UVa 11620 - City of Egocentrics

contents

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

Problem

在城市中有一群怪人，以自我為中心地方是居住，城市呈現一個網格，每一格表示居住人數。這些怪人自我為中心的判定方法有四種 水平、垂直、對角、反對角。

對於四種可能的線，選定線上一點，左側和右側的數量和會相同。輸出四種方法各自合適的居住地。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
3
3
1 2 3
4 5 6
7 8 9
3
1 1 1
1 1 1
1 1 1
4
5 7 7 6
2 4 0 8
6 1 0 7
6 8 7 5

Sample Output

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
H
V
D
0 2
2 0
A
0 0
2 2
H
0 1
1 1
2 1
V
1 0
1 1
1 2
D
0 2
1 1
2 0
A
0 0
1 1
2 2
H
2 2
V
1 2
2 2
D
0 3
1 1
1 2
3 0
A
0 0
2 1
2 2
3 3

Solution

利用前綴和在 O(1) 時間內檢查合法居住地，接著窮舉每一個地點即可。

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <stdio.h> 
#include <algorithm>
using namespace std;
const int MAXN = 128;
int A[MAXN][MAXN], B[MAXN][MAXN], n;
int mark[MAXN][MAXN];
void print(char c) {
    printf("%c\n", c);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            if (mark[i][j])
                printf("%d %d\n", i, j);
    }
}
void solve() {
    for (int i = 0; i < n; i++) {
        int sum = 0, l, r;
        for (int j = 0; j < n; j++)
            sum += A[i][j];
        l = 0, r = sum;
        for (int j = 0; j < n; j++) {
            r -= A[i][j];
            mark[i][j] = (l == r);
            l += A[i][j];
        }
    }
    print('H');
    
    for (int i = 0; i < n; i++) {
        int sum = 0, l, r;
        for (int j = 0; j < n; j++)
            sum += A[j][i];
        l = 0, r = sum;
        for (int j = 0; j < n; j++) {
            r -= A[j][i];
            mark[j][i] = (l == r);
            l += A[j][i];
        }
    }
    print('V');
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i-1 >= 0 && j-1 >= 0)
                B[i][j] = B[i-1][j-1] + A[i][j];
            else
                B[i][j] = A[i][j];
        }
    } 
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int l = 0, r = 0;
            if (i-1 >= 0 && j-1 >= 0)
                l = B[i-1][j-1];
            int ex, ey;
            ex = i + min(n-1-i, n-1-j), ey = j + min(n-1-i, n-1-j);
            r = B[ex][ey] - l - A[i][j];
            mark[i][j] = (l == r);
        }
    }
    print('D');
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i-1 >= 0 && j+1 < n)
                B[i][j] = B[i-1][j+1] + A[i][j];
            else
                B[i][j] = A[i][j];
        }
    } 
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int l = 0, r = 0;
            if (i-1 >= 0 && j+1 < n)
                l = B[i-1][j+1];
            int ex, ey;
            ex = i + min(n-1-i, j), ey = j - min(n-1-i, j);
            r = B[ex][ey] - l - A[i][j];
            mark[i][j] = (l == r);
        }
    }
    print('A');
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                scanf("%d", &A[i][j]);
        
        solve();
    }
    return 0;
}
/*
3
3
1 2 3
4 5 6
7 8 9
3
1 1 1
1 1 1
1 1 1
4
5 7 7 6
2 4 0 8
6 1 0 7
6 8 7 5
*/