解題區/解題區 - UVa

UVa 1105 - Coffee Central

contents

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

Problem

給一個網格狀的地圖，每一個地點都有其相對應的人數，現在要建造一個咖啡廳，而咖啡廳所在位置可以引來在曼哈頓距離為 m 以內的所有網格上的人數。

對於每一組詢問，回報咖啡廳應該建在哪裡可以引來最多的人。

Sample Input

1
2
3
4
5
6
7
8
9
10
4 4 5 3
1 1
1 2
3 3
4 4
2 4
1
2 
4
0 0 0 0

Sample Output

1
2
3
4
Case 1:
3 (3,4)
4 (2,2)
5 (3,1)

Solution

由於單一組詢問數量不到 20，想必可以使用 O(n^2) 去應付每一組詢問。

窮舉每一個可能的位置，並且去計算該位置能引來多少的人。為了加速統計人數，曼哈頓距離內，是一個 45 度的正方形，紀錄上非常不方便。利用旋轉矩陣，將整個平面紀錄轉 45 度，讓每一次的區域統計變成平行於兩軸的區域，如此一來就可以在 O(1) 時間內找到區域總和。

特別小心答案為人數 0 時，答案輸出的座標。

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAXN = 2048;
int sum[MAXN][MAXN];
void rotate(int x, int y, int &tx, int &ty, int dx, int dy) {
    tx = x - y + dy, ty = x + y;
}
void query(int limit, int dx, int dy) {
    int ret = 0, ret_x = 1, ret_y = 1;
    int tx, ty;
    for (int j = 1; j <= dy; j++) {
        for (int i = 1; i <= dx; i++) {
            rotate(i, j, tx, ty, dx, dy);
            int lx, rx, ly, ry, cnt;
            lx = max(tx - limit, 1);
            ly = max(ty - limit, 1);
            rx = min(tx + limit, dx + dy);
            ry = min(ty + limit, dx + dy);
            cnt = sum[rx][ry] - sum[rx][ly-1] - sum[lx-1][ry] + sum[lx-1][ly-1];
            if (cnt > ret) {
                ret = cnt, ret_x = i, ret_y = j;
            }
        }
    }
    printf("%d (%d,%d)\n", ret, ret_x, ret_y);
}
int main() {
    int dx, dy, n, q;
    int x, y, tx, ty, limit, cases = 0;
    while (scanf("%d %d %d %d", &dx, &dy, &n, &q) == 4 && dx) {
        // rotate matrix, rotate 45 degree
//		for (int i = 1; i <= dx; i++) {
//			for (int j = 1; j <= dy; j++) {
//				printf("(%d %d) -> (%d %d)\n", i, j, i - j + dy, i + j);
//			} 
//		}
        memset(sum, 0, sizeof(sum));
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &x, &y);
            rotate(x, y, tx, ty, dx, dy);
            sum[tx][ty]++;
        }
        
        for (int i = 1; i <= dx + dy; i++) {
            for (int j = 1, s = 0; j <= dx + dy; j++) {
                s += sum[i][j];
                sum[i][j] = sum[i-1][j] + s;
            }
        }
        
        printf("Case %d:\n", ++cases);
        for (int i = 0; i < q; i++) {
            scanf("%d", &limit);
            query(limit, dx, dy);
        }
    }
    return 0;
}