SRM 382, D1, 250-Pointer (CollectingRiders)

James S. Plank

Thu Nov 14 14:35:02 EST 2013
Updated: Thu Oct 22 17:06:16 EDT 2020

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
tests.sh. MD5 hash: eb1b20ea7ae3cb2d1b6c6c3794616138
answers.txt. MD5 hash: d6ecb2132848b7c30968ba46b3ee2fb6
Problem Given in Topcoder: 2007
Competitors who opened the problem: 437
Competitors who submitted a solution: 358
Number of correct solutions: 258
Accuracy (percentage correct vs those who opened): 59.0%
Average Correct Time: 27 minutes, 33 seconds.

In case Topcoder's servers are down

Here is a summary of the problem:

You are given a game board which is a rectangular grid.
You are given the location of "riders" on the board.
Each rider has a number from 1 to 9.
A 1-rider can move like a knight in chess during its move. In other words, if the 1-rider is at location (i,j), then it may move to any location (i±1,j±2) or (i±2,j±1), so long as that is a legal location.
An x-rider can make x moves like a knight in chess during its move. For example, if a 2-rider is at location (4,4), then it may move to location (4,8) in one move (a sub-move to (5,6), and then another sub-move to (4,8).
Your job is to return the minimum number of moves that it takes for every rider on the board to move to the same location.
Return -1 if it is impossible.
The topcoder constraints are that the board will have 1-10 rows and 1-10 columns. However, my tests.sh file will generate boards up to 30 by 30.
The board is given as a vector of strings, where each character is either a '.' to show that the location is empty, or a number from '1' to '9' to specify what kind of rider is there.
There may be any number of riders from 0 to having a rider on every location of the board.

The examples

Example 0:
```
{ "...1",
  "....",
  "2..." }
```
The answer is 2: The 2-rider can go from (2,0) to (0,1) to (2,2) as a first move. And then the 1-rider can go from (0,3) to (2,2) on its first move. That's a total of two moves.

Example 1:

{ "........",
  ".1......",
  "........",
  "....3...",
  "........",
  "........",
  ".7......",
  "........" }

The answer is 2: The 3 and 7 riders can both get to (1,1) in one move.

Example 2:
```
{ "..",
  "2.",
  ".." }
```
The answer is 0.
Example 3:
```
{ ".1....1." }
```
The answer is -1.

Example 4:

{"9133632343",
 "5286698232",
 "8329333369",
 "5425579782",
 "4465864375",
 "8192124686",
 "3191624314",
 "5198496853",
 "1638163997",
 "6457337215"}

The answer is 121.

Testing yourself

Like the Cryptography Problem, I have a shell script tests.sh, that you can use to test your program. When you run tests.sh, your answer should be identical to answers.txt.

Hints

Consider a "rider", and suppose that he can only do one jump per move. Then you can view the squares on the board as nodes on a graph, and you need to find the shortest distance from the rider's initial square to each square. The edges are knight moves. Therefore, in example zero, the graph is drawn below (I've colored the edges to make them easier to distinguish from one another):

Now, determine the shortest path from the rider in the upper right-hand corner to every other node:

And determine the shortest path from the rider in the lower left-hand corner to every other node:

Recall that this rider can do one or two jumps in every move. That means you can convert those shortest jumps to shortest moves by adding one and dividing by two. Why? Well, consider a node that a 1-rider can reach in two jumps. That means a 2-rider can reach it in one jump. (2+1)/2 = 1. Now, consider a node that a 1-rider can reach in three jumps. That means a 2-rider can reach it in two jumps. (3+1)/2 = 2. See how the math works? You'll have to derive the math for each kind of rider (it's not complex). Here is the graph for the 2-rider:

I'm going to redraw the two graphs here side by side -- the left one is the rider in the upper-right corner, and the right one is the rider in the lower-left corner:

For each node, add the two shortest distances. When you're done, you can see that the minimum node is two (there are two of them, and you can verify by hand that they work):

That gives you a nice roadmap towards solving this problem with BFS. Think about running time. Each BFS is O(|V|+|E|), which is O(r*c). There are up to r*c riders, so you have to do up to r*c BFS'. Therefore, the total is O(r*c*r*c). Since r and c are limited to ten, this is not a problem (and it's why I bumped it up to 30 in tests.sh).

When you're hacking up the BFS, think about how you want to represent the graph. I didn't represent edges explicitly. I simply simulated each jump when I processed a node during the BFS.