UVa 10748

From Algorithmist

Contents 1 10748 - Knights Roaming 2 Summary 3 Explanation 4 Optimizations 5 Input 6 Output

[edit] 10748 - Knights Roaming

• http://online-judge.uva.es/p/v107/10748.html

[edit] Summary

Knights Roaming is a problem involving a Breadth-First Search and some guesswork heuristics to get an acceptable speed.

[edit] Explanation

We are given the location of n < = 30 knights, each having a corresponding starting location and number of moves (x,y,k), where k < = 50. We need to determine how many different board locations the knights can cover.

The first thing to notice is that the board locations covered by different knights at a fixed distance have the same shape, they are just translated from one another. The next thing to notice is that the board locations reachable in k or less steps steps are a subset of reachable in k + 1 or less steps. Thus with a single 50 step Breadth-First Search we can determine the essential shape that every knight covers. From a single precomputed breadth first search, we can index board locations by the minimum distance it takes to reach them. So, for example, we will know that the points that are two moves away are (4, 2), (4, -2), (2, 4)...

However, the range of starting locations for the knights is quite large, in the range of - 10⁹ to 10⁹, so some sparse or compressed representation of the covered area is neccesary. A set of x, y pairs is a suitable representation.

One final note is that if you try insert every possible reachable location to a set of reachable points, you will timeout. One way to speed it up is to realize that in a single move, a knight moves exactly 3 manhattan steps away from it's start. Thus, the coverage from two knights which have manhattan distance 100 from each other, and one having 15 moves and the other having 10 moves cannot possibly interfere with one another, since . We can extend this idea to make our solution much faster. For each knight, let k_i be the number of moves for knight i, and d(i,j) be the manhattan distance from knight i to knight j. Compute for . Then, by the above reasoning, the points less than or equal to s_i moves away can be covered by only knight i, so the corresponding number of moves can simply be added into the number of covered cells without inserting them into the covered set.

[edit] Optimizations

See UsingHashMap for details on using an stl hash set as the sparse board representation.

[edit] Input

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

[edit] Output

5
33
155
1041150