SurroundArea
SRM 855 · 2024-05-22 · by misof
Problem Statement
Somebody used a thin pen to draw a big square divided into N by N unit squares. For example, for N = 3 the drawing would look as follows:
+---+---+---+
| | | |
+---+---+---+
| | | |
+---+---+---+
| | | |
+---+---+---+
You have a thick pen. You are going to start in the top left corner of the grid and trace some of the already existing grid lines to draw the boundary of a region that will consist of exactly A squares.
We will use the letters UDLR to denote the movement of your pen a unit of distance up, down, left, and right, respectively.
For example, for N = 3 and A = 6 one valid path your pen can follow is the path DDDRRRUULDLUUL. It traces the boundary of the following region with area 6:
+###+---+---+
# # | |
+---+---+###+
# # # #
+---+###+---+
# | | #
+###+###+###+
Formal requirements on your path:
- The path can never leave the N by N square: each step of the path must be along one of the already existing thin grid lines.
- A unit square counts as inside the region you are outlining if and only if it cannot be reached from the outside of the large square without crossing your path.
Among all such paths that outline a region of area exactly A, find the one with the shortest description and return it. If there are multiple optimal paths, you may return any one of them.
Notes
- Your path is not required to end where it started.
- Your pen may draw along the same grid segment multiple times. The segment still counts as drawn (regardless of the number of times it was traversed by your pen).
- While the options mentioned in the previous two notes are allowed, it is up to you to determine whether they are ever useful if your aim is to minimize the length of your path.
Constraints
- N will be between 1 and 500, inclusive.
- A will be between 1 and N*N, inclusive.
3 6 Returns: "DDDRRUUULL"
As in the problem statement, we have N = 3 and we want to surround a region with area A = 6. The way shown in the problem statement isn't optimal - drawing a simple 2x3 or 3x2 rectangle is better.
5 24 Returns: "RRRRDRDDDDLLLLLUUUUU"
Our path omits the unit square in the top right corner.
4 13 Returns: "DDRDRDRRUUUULLLL"
Our path draws the following region boundary: +###+###+###+###+ # | | | # +---+---+---+---+ # | | | # +###+---+---+---+ | # | | # +---+###+---+---+ | | # | # +---+---+###+###+ There are many other optimal paths. Some of them draw shapes that are not geometrically identical to the one shown above.
1 1 Returns: "DRUL"
2 1 Returns: "DRUL"
Submissions are judged against all 196 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SurroundArea with a public method string draw(int N, int A) · 196 test cases · 2 s / 256 MB per case