[Note to plug-in users: This problem statement contains images and superscripts. If you do not see the images, or
if 2k is displayed the same as 2k, then please view the problem in the applet.]
A Hilbert curve is a path that traces through all the points in a two-dimensional square grid
in such a way that each step in the path moves between neighbors in the grid. Hilbert curves
are sometimes used in image processing because they exhibit greater locality than
other common methods of linearizing a two-dimensional image, such as row-by-row (even
than the boustrophedonic variations of row-by-row that alternate between left-to-right
and right-to-left).
A rank-k Hilbert curve is a path through a 2k-by-2k grid.
A rank-1 Hilbert curve is a simple U-shape through a 2-by-2 grid, as shown below.
The blue point indicates the first point in the path and the red point indicates the
last point in the path. For k > 1, a rank-k Hilbert curve is
composed of four rank-(k-1) Hilbert curves, shown below as dotted lines.
Notice how the curve is organized in quadrants, first the upper left, then
the lower left, then the lower right, and finally the upper right. (The cross in the
background is not part of the curve; it merely highlights the quadrants.)
Notice also
how some of the rank-(k-1) curves are flipped and rotated compared to the
orientation of the rank-k curve. The blue and red points indicate
where each rank-(k-1) curve begins and ends, respectively. The overall rank-k
curve begins at the first point of the upper left rank-(k-1) curve and
ends at the last point of the upper right rank-(k-1) curve. Here is
a complete picture of a rank-3 Hilbert curve.
You will be given a value k and coordinates x and y in a
2k-by-2k grid. Coordinates range from 1 to 2k inclusive,
with the upper left corner at coordinates (1,1). Assuming the points are traversed
in the order specified by a rank-k Hilbert curve, determine how many steps it
takes to reach the point at coordinates (x,y). For example,
it takes 0 steps to reach the upper left corner at coordinates (1,1) and 4k-1
steps to reach the upper right corner at coordinates (2k,1).
| 