• 1394

## Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

## Goal

Your adventure path led you to an inn in a small, forgotten town somewhere to the North of Golem Hills.
After gulping the last drop from the 9th mug of elf wine a shady old man materializes out of nowhere, in-front of you.
You start to doubt the wine.
The old man (throwing a pack of old maps on the table): Do you want to earn some good coins?
You (without looking at him): I've enough for food and wine!
The old man: What about a whole inn...!
You: Hm...
The old man: Yeees and you'll get the glory of being the first one to get to this treasure!
You (looking at the bunch of maps): But they look the same!?
The old man: Or do they, you must choose wisely.
The voice of the old man (from nowhere): Ah right, one more thing, beware of the Dragons!
You grab your staff and sword, swallow one more whole mug of wine:
Well, it's glory time!

You are given N maps for a dungeon. Each map may contain a path to a treasure T, from starting position [ startRow; startCol ]. Determine the index of the map which holds the shortest path from the starting position to T, but be careful a map may lead you to a TRAP.

A path is marked on the map with ^, v, <, > symbols, each corresponding to UP, DOWN, LEFT, RIGHT directions respectively, i.e. each symbol shows you the next cell to move on.

A valid path must start from [ startRow; startCol ] and end on T.

The path length is the count of direction symbols plus 1, for the T cell.

Example:
W = 4 H = 4
startRow = 1 startCol = 1
N = 3

Maps:
`0.>>v.^#v..#v...T1.....v#..v#..>>T2....v<#.v.#...>T`

In the above example map 2 does not contain a valid path from [1; 1] to T, map 0 contains a valid path with length 7 (the count of the direction symbols + T) and map 1 contains a valid path with length 5, so the answer is 1.
Input
Line 1: Width W and height H of the maps
Line 2: startRow and startCol for the starting position on the map
Line 3: An integer N for the number of maps to check
N * H Lines: Each H consecutive lines are representing a single map. Each line contains W characters representing a row of a map.

Characters can be:
`. - Empty square# - Wall^ - Move UPv - Move DOWN< - Move LEFT> - Move RIGHTT - The treasure square`
Output
index of the map with the shortest path. If there isn't a map with valid path from [ startRow; startCol ] to T output TRAP.
Constraints
There is always a T on the maps.
If there are maps with valid path from [ startRow; startCol ] to T only one map holds the shortest path.
The given maps are representing the same dungeon, but the position for T may differ.
0 < N < 10
2 < W, H < 20
Example
Input
```4 4
1 1
3
.>>v
.^#v
..#v
...T
....
.v#.
.v#.
.>>T
....
v<#.
v.#.
..>T```
Output
`1`

A higher resolution is required to access the IDE