Problem L
Where Am I Now?
Who am I? What am I? Why am I? These are all difficult questions that have kept philosophers reliably busy over the past millennia. But when it comes to “Where am I?”, then, well, modern smartphones and GPS satellites have pretty much taken the excitement out of that question.
But what if you have no GPS at hand? In one of the World Finals 2021 problems, the Instant Cartographic Positioning Company (ICPC) demonstrated a way to determine your current location using spiral movements and observing your surroundings. Unfortunately, their method can only be used in open areas where you can move freely without any obstacles. What if you need to locate your exact position in a closed space? How can you do it? Well, now is the time to find out.
You are given a map of an area consisting of unit squares, where each square is either open or occupied by a wall. At the beginning, you are placed in one of the open unit squares, but you do not know which square it is or what direction you face. Any two individual open spaces are indistinguishable, and likewise for walls. You may walk around the area, at each step observing the distance to the next wall in the direction you face. The goal is to determine your exact position on the map.
Interaction
The first line of input contains two integers $r$ and $c$ ($1 \le r,c \le 100$) specifying the size of the map. This is followed by $r$ lines, each containing $c$ characters. Each of these characters is either a dot (.) denoting an open square, or a number sign (#) denoting a square occupied by a wall.
At least one of the squares is open. You know you start in one of the open squares on the map, facing one of the four cardinal directions, but your position and direction is not given in the input. All squares outside the map area are considered walls.
Interaction then proceeds in rounds. In each round, one line becomes available, containing a single integer $d$ ($0\le d\le 99$) indicating that you see a wall in front of you at distance $d$. This means there are exactly $d$ open squares between your square and the closest wall in the current direction. You should then output a line containing one of the following:
-
left to turn 90 degrees to the left,
-
right to turn 90 degrees to the right,
-
step to move one square forward in your current direction,
-
yes $i$ $j$ to claim that your current position is row $i$, column $j$ ($1 \le i \le r$, $1 \le j \le c$),
-
no to claim that no matter what you do, it will not be possible to reliably determine your position.
If you output yes or no, interaction stops and your program should terminate. Otherwise, a new interaction round begins. In order to be accepted, your solution must never step into a wall, and can run for at most $100\, 000$ interaction rounds (the final round where you only report yes or no counts towards this limit).
| Read | Sample Interaction 1 | Write |
|---|
3 3 ##. #.. ... 1
right
1
step
0
left
0
right
0
right
1
yes 2 2
| Read | Sample Interaction 2 | Write |
|---|
3 5 ##.## ###.# .#.## 0
left
0
no
| Read | Sample Interaction 3 | Write |
|---|
2 1 # . 0
yes 2 1