Problem J
Find Holger Danske
Languages
da
en
I dit sommerferiejob viser du turister rundt på Kronborg slot. De fleste vil gerne se Holger Danskes statue, som befinder sig i Kronborgs labyrintiske kældre. Her sover han så dybt, at hans skæg er vokset fast til stenbordet i Kronborgs kælder. Men han vil vågne op til dåd, hvis Danmark kommer i nød.
Desværre er du ofte selv i tvivl om, hvorhenne statuen står, og må ofte gå store omveje for at finde ham. Derfor vil du lave en huskeseddel med en korteste vej fra indgangen til Holgers statue.
Indgangen er i Kronborgs nordvestlige hjørne. Du begynder ved indgangen og kigger mod øst.
Input
På første linje står to heltal $N$ og $L$, som angiver dimensionerne på Kronborgs labyrint. Der gælder $3\leq N\leq 100$ og $3\leq L \leq 100$. Herefter følger $N$ linjer, hver af længde $L$. Linjerne består af tegn, der beskriver Kronborgs kældre. Dobbeltkryds »#« betyder »væg« og punktum ».« betyder »ingen væg«. Holger Danskes position er angivet ved et enkelt »H«.
Indgangen er i det nordvestlige hjørne, som vist i eksemplerne, hvor der garanteret står ».«. Alle andre felter på randen er vægge. Det er garanteret, at Holger kan nås fra indgangen.
Output
En følge af retningsangivelser ^<>, som skal betyde henholdsvis »gå et felt frem«, »drej til venstre« og »drej til højre«. Du skal angive en vej som bruger så få »^« som muligt. Hvis der er flere optimale svar, kan du angive hvilket som helst af dem.
| 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# #### |
^>^<^ |
