It worked! Oh wait... Detective Pikaptcha is now trapped in a more advanced type of space-warp maze. It looks like a ring but twisted. It doesn’t take long for Pikaptcha to realize that the maze is actually a gigantic Möbius strip.
“Let’s try the same method...”Your objective is to write a program that will compute, for each cell of a maze, the number of times Pikaptcha will step into the cell by following a wall until he reaches his original location.
Pikaptcha looked up his database which responded, "A Möbius strip is a surface with only one side and only one edge." But wait...Pikaptcha found that this one is not the standard Möbius because the edge is gone. It is a variant having one endless looping surface and no edge. Pikaptcha can cross the edge to go to the other side of the strip if it is not blocked by walls.
The Möbius strip maze is given to you as a grid filled with
Here are instructions to create a real-world representation of a Möbius maze:
- Print the first half (along the x-axis) of the grid on a piece of paper.
- Flip the paper over vertically.
- Print the rest of the grid on the side now in front of you.
- Give the strip a half-twist and connect the two ends to create a loop.
>: facing right
v: facing down
<: facing left
^: facing up
Rfor the wall on his right
Lfor the wall on his left
We’re considering the
Allotted response time to output is ≤
A higher resolution is required to access the IDE