Frieren wants to become a Dragon Warrior, like Po
As she determines to become one, she needs to learn the "Dragon Curve" kung fu style
What is Dragon Curve?
This is a Dragon Curve (Wikipedia)
https://upload.wikimedia.org/wikipedia/commons/a/a9/Dragon_Curve_unfolding_rectangular_numbered.gif <= [Open to see the GIF]
Initially, there is only 1 stick
The next pattern is copying the previous pattern and rotating by 90 degree
As the pattern can go infinte, we can calculate what the patterns will be in a certain position
Question :
Let every stick length be 3x1, black boxes, and based on the dragon curve pattern, let :
Index 1 is the first stick of the pattern,
Index 2 is the second stick of the pattern,
Index 3 is the third stick of the pattern,
and so on … until infinity
Given the pattern length is n and the pattern start at index s,
You need to draw the dragon curve start from index s until index s + n - 1, as the length of the pattern is n in the 2d array
The '#' indicates the pattern (Black), while the blank is '.' represents the blank (White)
The drawing must fit perfectly in the array, which means:
The given pattern must fully be shown in the array
The most left/right column and most up/down row can't be a blank row/column
Sample IO Explanation :
Note : If the gray box is inside the array, leave it as white '.'
You can imagine every stick has their own direction from the starting point. For example:
And as you can observe, for every pattern with length of 2k as k ≥ 0 is integer, then the next 2k pattern (from 2k+1 until 2k+1) is basicly the same direction as previous pattern with mirrored index, and rotated by 90 degree. You can see GIF below demonstrating how do you know the pattern start from index 1, starting from red point
Since the starting index start could be any number in range 1018, there is no way we use bottom-up approach, as it's very slow to calculate 1 by 1, then we are using top-down approach.
To make the array of the board: