HorsesGoHome
SRM 824 · 2022-02-17 · by misof
Problem Statement
A horizontal 2D plane is covered by an infinite chessboard. There are some horses scattered on the chessboard: for each valid i, there is one horse in row HR[i], column HC[i].
The horses move just like chess knights: in each move it can jump from its current square (r1,c1) to any other square (r2,c2) such that the differences |r1-r2| and |c1-c2| are 2 and 1, in either order. Thus, on an infinite chessboard each horse always has 8 potential moves.
At any time, each square of the chessboard may only contain one horse. Moves that would take a horse into an already occupied square aren't allowed.
At the origin of the coordinate system there is a special 8x8 chessboard consisting of rows and columns with numbers between 0 and 7, inclusive. This chessboard is called the stable.
Find the minimum number M of moves needed to put all the horses into the stable.
If M is greater than 500, return {M}.
Otherwise, return a
Notes
- A valid solution always exists and for the constraints used the optimal M always fits into a signed 32-bit integer variable.
Constraints
- HR will contain between 1 and 64 elements, inclusive.
- HC will contain the same number of elements as HR.
- Each coordinate in the input will be between -10^7 and 10^7, inclusive.
- No two horses will start on the same square.
{3, 1, 4, 1, 5, 2, 6}
{5, 3, 5, 7, 3, 0, 4}
Returns: {0 }
All these horses are already in the stable. No moves necessary.
{9, 9}
{8, 11}
Returns: {4, 9, 8, 7, 7, 9, 11, 7, 10, 7, 10, 5, 9, 5, 9, 4, 7 }
The first horse can reach the stable in a single jump, the second one can do so in two jumps. However, this would require both of them to end on the same square (7, 7), which is not allowed. Thus, the best solutions require four jumps.
{9, 8}
{10, 8}
Returns: {3, 8, 8, 7, 6, 9, 10, 8, 8, 8, 8, 6, 7 }
Note that move order may matter. If you want to do the moves shown in the example output, you need to make sure that you move the second horse from (8, 8) into the stable before moving the first horse to (8, 8).
{-1234567}
{-1234567}
Returns: {823045 }
{-1, -1, -1, -1, -1, -1, -1, -1, 8, 8, 8, 8, 8, 8, 8, 8, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7}
{0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, -1, -1, -1, -1, -1, -1, -1, -1, 8, 8, 8, 8, 8, 8, 8, 8}
Returns: {32, -1, 0, 0, 2, -1, 1, 0, 3, -1, 2, 1, 3, -1, 3, 1, 2, -1, 4, 1, 5, -1, 5, 1, 4, -1, 6, 0, 4, -1, 7, 0, 5, 8, 0, 6, 1, 8, 1, 6, 0, 8, 2, 6, 3, 8, 3, 6, 2, 8, 4, 6, 5, 8, 5, 6, 4, 8, 6, 6, 7, 8, 7, 6, 6, 0, -1, 1, 1, 1, -1, 0, 1, 2, -1, 0, 0, 3, -1, 1, 0, 4, -1, 2, 0, 5, -1, 3, 0, 6, -1, 4, 0, 7, -1, 5, 0, 0, 8, 1, 6, 1, 8, 0, 6, 2, 8, 0, 7, 3, 8, 1, 7, 4, 8, 2, 7, 5, 8, 3, 7, 6, 8, 4, 7, 7, 8, 5, 7 }
Thirty-two horses, starting on all 32 squares that share a side with the stable. It is possible to make just one jump with each of them and choose their destinations so that they end on 32 distinct squares inside the stable.
Submissions are judged against all 109 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class HorsesGoHome with a public method vector<int> move(vector<int> HR, vector<int> HC) · 109 test cases · 2 s / 256 MB per case