TwoDimensionalSort

2022 TCO Round 3 · 2022-04-14 · by misof

2022 TCO Round 3 · 2022-04-14 · by misof · Greedy, Sorting

Show categories

Class Name: TwoDimensionalSort

Return Type: int[]

Method Name: sortLetters

Arg Types: (vector<string>)

Problem Statement

There is a square board divided into 26x26 unit square cells. Both rows and columns of the board are numbered starting from zero.

On the board there are some white chess rooks. A rook is a piece that can move horizontally or vertically. The whole move must go in one direction. All cells visited during the move (including the final cell where the move ends) must be empty.

Each rook is labeled with a different uppercase English letter ('A'-'Z'). Thus, there are at most 26 rooks.

You are given the description of the board in the String[] board. Each character in board represents one cell: board[r][c] is the character in row r, column c of the board. The rooks are described by their label, empty cells are denoted '.' (period).

Your task is to sort the rooks.

The row major order of cells on the board is formed by taking all cells in row 0 (left to right), then all cells in row 1 (again, left to right), and so on until the last row.

A board with rooks is considered sorted if the row major order of cells has all the rooks in alphabetical order.

In human words, just imagine reading board as a block of text. On a sorted board the rook letters will appear in sorted order, smallest to largest.

Find any sequence of at most 60 valid rook moves that will transform the given board into a sorted board.

If your sequence consists of N moves, return a int[] with 4*N elements: for each move, output four integers {r1, c1, r2, c2} meaning that you want to take the rook in row r1, column c1 and move it to row r2, column c2.

(Your return value should be the concatenation of all those int[]s, in the order in which you want to perform them.)

Notes

Any valid solution will be accepted.
It is not required to minimize the number of moves.
Remember that each valid move must be horizontal or vertical, and that valid moves cannot go through cells that contain other rooks.
As a technicality, moves with distance 0 (i.e., taking a rook and leaving it where it is) are allowed.

Constraints

board will contain exactly 26 elements.
Each element of board will contain exactly 26 characters.
Each character in board will be either '.' or an uppercase English letter.
All letters in board will be distinct.

Examples

{"..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 ".........................."}
Returns: { }

An empty board is already sorted. Not only are there no moves necessary, there are actually no moves possible. Thus, the empty int[] is the only valid answer for this test case.

{"..........................",
 "..........................",
 "......B...................",
 "..............Q...........",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 ".........................."}
Returns: {3, 14, 3, 17 }

This board is also sorted: in row major order we will encounter 'B' before 'Q'. Our example solution moves the 'Q' rook a few cells to the right, just to illustrate that minimizing the number of moves is not necessary.

{"..........................",
 "..........................",
 "..........................",
 ".....BCDE.................",
 ".....F....................",
 ".....G.A..................",
 ".....H....................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 ".........................."}
Returns: {5, 7, 5, 9, 5, 9, 2, 9 }

Rook 'A' is the only one violating sorted order. We can fix that. In the example solution we move this rook two cells right, and then as our second action we move it three cells up.

{"..........................",
 "..........................",
 "..........................",
 ".....BCED.................",
 ".....F....................",
 ".....G.A..................",
 ".....H....................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 "..........................",
 ".........................."}
Returns: {3, 7, 2, 7, 2, 7, 2, 11, 5, 7, 0, 7, 2, 11, 3, 11 }

Here, rooks 'E' and 'D' are also in incorrect order. Our solution makes two moves with the 'E' rook, then one move with the 'A' rook, and finally a third move with the 'E' rook. The final configuration of rooks is shown below. {".......A..................", "..........................", "..........................", ".....BC.D..E..............", ".....F....................", ".....G....................", ".....H....................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", ".........................."}

{"C.........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", "..........................", ".........................."}
Returns: {0, 0, 2, 0 }

Submissions are judged against all 151 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TwoDimensionalSort with a public method vector<int> sortLetters(vector<string> board) · 151 test cases · 2 s / 256 MB per case