409203: GYM103456 F Maze Escape Pt. I

Ali is preparing for a new game, involving a complex maze filled with dangerous hazards. Luckily, Ali has access to useful intel in the form of a map of the maze, telling him which of the of the four directions (up ^, down v, left <, or right >) he should move in given the current location to avoid a hazard. Additionally, some locations in the maze are marked O on the map as rescue points, where if a contestant can make it there, she will be safely extracted from the treacherous game.

Help Ali evaluate his odds of safely escaping the maze! Count the number of locations in the maze where if Ali starts at that location and follows the directions on his secret map, he will make it safely to a rescue point.

The first line of input contains two space-separated integers $$$R$$$ and $$$C$$$ ($$$1\leq R, C \leq 10^3$$$), denoting the number of rows and columns in the maze respectively. $$$R$$$ lines follow, each containing $$$C$$$ characters where each character will be one of five possibilities: < to indicate that Ali should move left, > to indicate that he should move right, ^ for him to move up, and v for him to move down in the maze. Lastly, O denotes a rescue point where Ali could make it out alive if he got there.

Print the number of locations in the maze where if Ali started there, he could be certain to make it to a rescue point. Note, Ali could start out at any location in the maze, including at a rescue point.

3 7
>>v>>>v
O<<^v^<
^><v>O^

10