RoomPairs
TCO20 Round 2B · 2020-04-13 · by misof
Problem Statement
There is a building. Its floor is a R times C rectangle divided into a grid of unit squares. You are going to build walls along the sides of some unit squares. This will divide the building into one or more rooms. Two rooms are adjacent if they share a common wall segment. (Touching corners are not enough.)
Can you build the walls in such a way that there will be exactly N pairs of adjacent rooms?
If yes, find and return any valid solution and return its ASCII art drawing as a
See the Examples for the proper output format. A formal definition is given in the Notes but should not be needed.
Notes
- The ASCII art must have 2*R+1 rows and 2*C+1 columns.
- Each character with both (0-based) coordinates even must be '+'. These characters represent corners of unit squares.
- Each character with both (0-based) coordinates odd must be ' '. These characters represent the individual unit squares.
- Each character with coordinates [even][odd] must be either ' ' (representing the absence of a wall) or '-' (representing the presence of a wall).
- Each character with coordinates [odd][even] must be either ' ' (representing the absence of a wall) or '|' (representing the presence of a wall).
- Characters on the boundary cannot be spaces. These characters represent the outer wall of the building.
Constraints
- R will be between 1 and 30, inclusive.
- C will be between 1 and 30, inclusive.
- N will be between 0 and R*(C-1) + (R-1)*C, inclusive.
2
4
1
Returns: {"+-+-+-+-+", "| | | |", "+ + +-+ +", "| | |", "+-+-+-+-+" }
Formatted output: {"+-+-+-+-+", "| | | |", "+ + +-+ +", "| | |", "+-+-+-+-+"} There are only two rooms, they form one pair of adjacent rooms. Note that the bigger room contains one extra wall that does not change anything. This is allowed.
3
3
4
Returns: {"+-+-+-+", "| | | |", "+-+ +-+", "| |", "+-+ +-+", "| | | |", "+-+-+-+" }
Formatted output: {"+-+-+-+", "| | | |", "+-+ +-+", "| |", "+-+ +-+", "| | | |", "+-+-+-+"} The big middle room is adjacent to each of the four small rooms.
3
4
3
Returns: {"+-+-+-+-+", "| |", "+ +-+-+ +", "| | | | |", "+ +-+-+ +", "| |", "+-+-+-+-+" }
4
5
31
Returns: {"+-+-+-+-+-+", "| | | | | |", "+-+-+-+-+-+", "| | | | | |", "+-+-+-+-+-+", "| | | | | |", "+-+-+-+-+-+", "| | | | | |", "+-+-+-+-+-+" }
1
1
0
Returns: {"+-+", "| |", "+-+" }
Submissions are judged against all 309 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RoomPairs with a public method vector<string> construct(int R, int C, int N) · 309 test cases · 2 s / 256 MB per case