Problem J
Find Holger Danske
Languages
da
en
In your summer job, you guide tourists around Kronborg Castle in Elsinore. Most visitors want to see the statue of Holger Danske, which is located in the labyrinthine cellars of Kronborg. Here he sleeps so deeply that his beard has grown into the stone table in Kronborg’s cellar. But he will awaken to action when Denmark is in need.
Unfortunately, you often find yourself unsure of the statue’s whereabouts and must then take long detours to find him. Therefore, you want to write down the directions with the shortest route from the entrance to Holger’s statue.
The entrance is in the northwest corner of Kronborg. You start at the entrance looking east.
Input
The first line contains two integers $N$ and $L$, indicating the dimensions of Kronborg’s labyrinth. We have $3\leq N\leq 100$ and $3\leq L \leq 100$. Following this are $N$ lines, each of length $L$. The lines consist of characters describing Kronborg’s cellars. Pound sign “#” means “wall” and period “.” means “no wall”. Holger Danske’s position is indicated by a single “H”.
The entrance is in the northwest corner, as shown in the examples, where there is guaranteed to be a “.”. All other fields on the edge are walls. It is guaranteed that Holger can be reached from the entrance.
Output
A sequence of directional indicators ^<>, meaning respectively “move one step forward”, “turn left”, and “turn right”. You should provide a route that uses as few “^” as possible. If there are multiple optimal solutions, you can provide any of them.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 3 ### .H# ### |
^ |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 3 ### ..# #H# ### |
^>^ |
| Sample Input 3 | Sample Output 3 |
|---|---|
5 5 ##### ....# #.#.# #.H.# ##### |
^>^^<^ |
| Sample Input 4 | Sample Output 4 |
|---|---|
6 9 ######### ..#...#H# #...#.#.# #.###.#.# #.......# ######### |
^>^^^<^^^^^^<^^^ |
| Sample Input 5 | Sample Output 5 |
|---|---|
4 4 #### ...# #.H# #### |
^>^<^ |
