407909: GYM102939 G Ski-Bot 3000

Every year, hundreds of skiers compete in an annual World Cup alpine ski race called the Hahnenkammrennen. Over the course of a weekend, skiers conquer several demanding slopes down the Hahnenkamm mountain and race to achieve the fastest times.

This year, to keep things "interesting" of course, the ski slopes have been scattered with various obstacles to block skiers' paths, such that they must dodge these hazards or surely get knocked out of the competition. To compensate for possible time delays caused by the hazards, ramps have also been added to the course, enabling skiers to launch into the air and sail over obstacles, traveling quickly without being slowed by the friction of snow.

This is also the first year that robots will be allowed to compete in the Hahnenkammrennen. You are determined to capitalize on this opportunity and win the World Cup with the first ever bot competitor: the Ski-Bot 3000. The hardware components for Ski-Bot have already been assembled, but now it must be able to navigate the fastest possible path down each slope that it faces.

Write a program for the Ski-Bot 3000 that, given an overhead map of a ski slope course from the Hahnenkammrennen, computes the length of the shortest path from the top to the bottom of the course. And hurry—the first race starts today!

The first line of input contains two integers, $$$N$$$ and $$$M$$$ ($$$1 \leq N,M \leq 1000$$$), denoting the number of rows and columns in the rectangular ski slope map respectively.

$$$N$$$ lines follow, each containing $$$M$$$ characters denoting grid cells on the ski slope map. A # character denotes an obstacle cell that cannot be skied across. A . denotes clear snow that can readily be traversed. Lastly, a > denotes a wooden ramp that will launch a skier upwards, such that they land on the next clear cell ahead of them down the slope.

The leftmost column of the grid represents the top of the slope, and the rightmost column represents the base. Skiers can choose to start in any clear cell at the top of the slope and likewise cross the course finish-line in any clear cell at the base.

Movement-wise, a skier can only ever ski downhill, or right-ward on the map. This means that if a skier is located on a clear cell in row $$$r$$$ and column $$$c$$$ on the slope map, their only next options are to ski into cells $$$(r+1, c+1)$$$, $$$(r, c+1)$$$, or $$$(r-1, c+1)$$$. Of course, if a skier reaches a ramp cell, their next move is to get launched into the air and land on the first clear cell down-slope from their current position. Note that each ramp cell is guaranteed to have a clear landing spot downhill on the course.

Print the length of the shortest path from top to bottom of the ski slope (left to right on the map). Note that each movement from cell to cell counts as a single path step, including a ramp jump which counts as only one step, regardless of how many obstacle cells or ramps a skier jumps over before she lands. You are guaranteed that a path down the slope is always possible.

3 14
..##..##.>##..
......#.##.#..
.#...#....#...

11

5 15
.#..##.>#####..
.###.....#.>##.
....##.>#.###..
##.>##>#...###.
.##>#.>#.##....

8