QueenMeetup
SRM 766 · 2019-09-09 · by misof
Problem Statement
You have a d times d chessboard. Both rows and columns of the chessboard are numbered starting from 0. There are n queens on the board: for each i from 0 to n-1, queen number i is located at coordinates (r[i], c[i]).
The queens would like to meet. That is, they would like to occupy positions that form an 8-connected component. (See Notes for all definitions.)
Find and return any valid sequence of 50 or fewer valid moves that accomplishes this goal.
Suppose that we describe each move as follows: "take queen number q[j] and move her to the coordinates (nr[j], nc[j]).
Return the following
Notes
- A chess queen can move horizontally, vertically, or diagonally. In each move she can move arbitrarily far, as long as all cells along her way are empty. Note that in this problem the destination cell must also be empty, as our queens cannot take each other.
- A valid move of a queen must actually move the queen. In other words, a move that starts and ends on the same coordinates is not a valid move.
- A chess king can move in the same eight directions as a chess queen, but only by a single square.
- A set S of cells on the chessboard is called 8-connected if it has the following property: a chess king can reach any cell in S from any other cell in S by a sequence of valid moves that never steps outside of S.
- There is always a solution.
Constraints
- d will be between 5 and 10^9, inclusive.
- r will have between 1 and 20 elements, inclusive.
- c will have the same number of elements as r.
- Each element of r will be between 0 and d-1, inclusive.
- Each element of c will be between 0 and d-1, inclusive.
- The cells occupied by the queens will be distinct.
5
{0, 1, 3}
{0, 1, 3}
Returns: {0, 2, 0, 0, 2, 2 }
The queens start as follows: 0.... .1... ..... ...2. ..... Our solution first moves queen 0 to row 2 and then to column 2, obtaining the following 8-connected configuration: ..... .1... ..0.. ...2. ..... Note that queen 0 could not go from its original location to its final location in a single move, as queen 1 is in the way.
5
{0, 0, 4, 4}
{0, 4, 4, 0}
Returns: {2, 1, 1, 3, 2, 0, 1, 0, 1 }
Initial configuration: 0...1 ..... ..... ..... 3...2 Final configuration: 01... .2... 3.... ..... .....
1000
{42}
{47}
Returns: { }
Nothing needs to be done in this case, all queens are already together.
1234567
{123456, 123457, 123456}
{654321, 654322, 654323}
Returns: { }
This triple of queens is also already a valid solution.
100
{4, 2, 10, 5, 1, 3, 9, 17}
{0, 1, 2, 3, 4, 5, 6, 7}
Returns: {0, 0, 0, 1, 0, 1, 2, 0, 2, 3, 0, 3, 4, 0, 4, 5, 0, 5, 6, 0, 6, 7, 0, 7 }
As these queens are in distinct but adjacent columns, our solution simply moves all of them to row 0.
6
{0, 1, 3}
{0, 1, 3}
Returns: {2, 2, 2 }
A configuration similar to the one from Example 0, but now we produced a different solution.
Submissions are judged against all 186 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class QueenMeetup with a public method vector<int> move(int d, vector<int> r, vector<int> c) · 186 test cases · 2 s / 256 MB per case