解題區/解題區 - UVa

UVa 10748 - Knights Roaming

contents

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

Problem

給予無限大盤面上，每一個騎士擁有自己的起始位置、限定走 k 步，請問盤面上有多少騎士可以抵達的點座標。

Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
5
1 1 0
2 2 0
3 3 0
4 4 0
5 5 0
5
1 1 1
2 2 1
3 3 1
4 4 1
5 5 1
4
-1 -1 2
2 2 1
3 3 3
4 4 3
0

Output

1
2
3
5
33
155

Solution

對於所有騎士同時運行 Bfs 很容易造成 TLE。這裏介紹其中一種優化策略，對於獨立的騎士直接計算可抵達的地點總數 (預處理只有一個騎士的盤面的答案)。

獨立騎士能步行的範圍為曼哈頓距離在 3 k[i] 內的所有點，對於兩兩騎士做交集判定，若不存在任何重疊區域，則該騎士為獨立。

為了加速運算，可以使用 hash 來防止重複運算，或者平移座標到可以在 500 x 500 內的陣列中做 Bfs。

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <stdio.h> 
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
const unsigned int hash_mod = 100019;
set< pair<int, int> > R[hash_mod];
unsigned int hash(int x, int y) {
    unsigned int a = 63689, b = 378551;
    unsigned int value = 0;
    int c[4] = {x, y, y, x};
    for (int i = 0; i < 4; i++) {
        value = value * a + c[i];
        a *= b;
    }
    return value % hash_mod;
}
const int dx[] = {1, 1, -1, -1, 2, 2, -2, -2};
const int dy[] = {2, -2, 2, -2, 1, -1, 1, -1};
int bfs(int sx[], int sy[], int dstep[], int n) {		
    for (int i = 0; i < hash_mod; i++)
        R[i].clear();
        
    queue<int> X[64], Y[64];
    int step, tx, ty, x, y;
    
    for (int i = 63; i >= 0; i--) {
        for (int j = 0; j < n; j++) { 
            if (dstep[j] == i) {		
                X[i].push(sx[j]), Y[i].push(sy[j]);
                R[hash(sx[j], sy[j])].insert(make_pair(sx[j], sy[j]));
            } 
        } 
        while (!X[i].empty()) {
            x = X[i].front(), X[i].pop();
            y = Y[i].front(), Y[i].pop();
            
            if (i == 0)	continue;
            for (int k = 0; k < 8; k++) {
                tx = x + dx[k], ty = y + dy[k];
                if (!R[hash(tx, ty)].count(make_pair(tx, ty))) {
                    R[hash(tx, ty)].insert(make_pair(tx, ty));
                    X[i-1].push(tx), Y[i-1].push(ty);
                }
            }
        }
    }	
    
    int ret = 0;	
    for (int i = 0; i < hash_mod; i++)
        ret += R[i].size();
    return ret;
}
int main() {
    int x[64], y[64], step[64];
    int n;
    int h[64] = {};
    for (int i = 0; i <= 50; i++) {
        x[0] = y[0] = 0, step[0] = i;
        h[i] = bfs(x, y, step, 1);
    }
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++)
            scanf("%d %d %d", &x[i], &y[i], &step[i]);
        
        int independent = 0;
        for (int i = 0; i < n; i++) {
            int d = 0x3f3f3f3f;
            for (int j = 0; j < n; j++) {
                if (i == j)	continue;
                d = min(d, max(abs(x[i] - x[j]) + abs(y[i] - y[j]) - 3 * (step[i] + step[j]), 0));
            }
            if (d > 0)
                independent += h[step[i]], step[i] = -1;
        }
                
        int ret = bfs(x, y, step, n) + independent;
        printf("%d\n", ret);
    }
    return 0;
}
/*
5
1 1 0
2 2 0
3 3 0
4 4 0
5 5 0
5
1 1 1
2 2 1
3 3 1
4 4 1
5 5 1
4
-1 -1 2
2 2 1
3 3 3
4 4 3
30
0 0 50
1 1000 50
2 2000 50
3 3000 50
4 4000 50
5 5000 50
6 6000 50
7 7000 50
8 8000 50
9 9000 50
10 10000 50
11 11000 50
12 12000 50
13 13000 50
14 14000 50
15 15000 50
16 16000 50
17 17000 50
18 18000 50
19 19000 50
20 20000 50
21 21000 50
22 22000 50
23 23000 50
24 24000 50
25 25000 50
26 26000 50
27 27000 50
28 28000 50
29 29000 50
*/