DirectionBoard
TCO13 Round 1A · 2013-02-19 · by gojira_tc
TCO13 Round 1A · 2013-02-19 · by gojira_tc · Graph Theory
Problem Statement
Problem Statement
A direction board is a matrix filled with arrows. Each arrow occupies one cell and points in one of the four directions: left, right, down, up. Each cell has two coordinates (row, column), starting with (0, 0) in the top left corner. Given a starting cell (r, c), you can move through the board in the following way. First, check the arrow in cell (r, c). If it points left, move left of the current cell, i.e. into cell(r, c - 1). For the right arrow, move to (r, c + 1). Up goes to (r - 1, c) and down to (r + 1, c). Each row and column of the board is cyclic, so whenever the new cell is outside the board, you appear on the other side. For example, moving left from (3, 0) on a board of size 5 by 5 results in appearing in cell (3, 4).
You need a board such that for every starting cell you always return to it during the movement process. If the given board does not satisfy this condition, you can change the direction of the arrow in any cell. For example, look at the following boards. In the left one, one only returns to the initial cell when he begins in cells (1, 1), (1, 2), (2, 0), (2, 3). After redirecting two arrows, you obtain a board with the given property.
Find the minimum number of arrow redirections which transforms the given board into a valid one.
You need a board such that for every starting cell you always return to it during the movement process. If the given board does not satisfy this condition, you can change the direction of the arrow in any cell. For example, look at the following boards. In the left one, one only returns to the initial cell when he begins in cells (1, 1), (1, 2), (2, 0), (2, 3). After redirecting two arrows, you obtain a board with the given property.
Find the minimum number of arrow redirections which transforms the given board into a valid one.
Constraints
- board will contain between 1 and 15 elements, inclusive.
- Each element of board will contain between 1 and 15 characters, inclusive.
- All elements of board will be of the same length.
- Each element of board will consist of characters from the set {'L', 'R', 'U', 'D'} only.
Examples
0)
{"RRRD",
"URDD",
"UULD",
"ULLL"}
Returns: 0
This board is already good. No matter which cell you start in, you always you return to it.
1)
{"RRRD",
"URLL",
"LRRR"}
Returns: 2
The example from the problem statement.
2)
{"RRD",
"URD",
"ULL"}
Returns: 2
This board is not valid, because if one starts from (1, 1), he never returns to this cell. A possible solution with only two changes:
3)
{"ULRLRD",
"UDDLRR"}
Returns: 4
4)
{"UDLRLDLD",
"DLDLLDLR",
"LLLLLDLD",
"UUURRRDD"}
Returns: 9
Submissions are judged against all 111 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class DirectionBoard with a public method int getMinimum(vector<string> board) · 111 test cases · 2 s / 256 MB per case