409205: GYM103456 H Maze Escape Pt. II

Once again, Ali knows that the next game he must face in Squid Game will be a dangerous maze, riddled with perils at every turn. He has another map of the maze, providing intel on how to move in each location to avoid hazards. However, this time there aren't any rescue points inside the maze–contestants must completely leave the maze grid in order to reach safety.

Ali knows that if he isn't careful when trying to navigate the maze, he might be too busy avoiding hazards to actually escape. Specifically, if all Ali does is follow the direction instructions at each location, he might find himself in an infinite loop that will never escape the maze. Because of this issue, Ali wants to know the number of unordered pairs of distinct locations in the maze such that both locations are reachable if Ali starts at the opposite location in the pair and follows the intel. Can you write a program to calculate the answer?

The first line consists of two integers $$$R$$$ and $$$C$$$ $$$(1 \leq R, C \leq 300)$$$, which give the number of rows and columns of the maze.

The next $$$R$$$ lines consist of $$$C$$$ characters which are all either $$$\texttt{^}, \texttt{v}, \texttt{<}, \texttt{>}$$$ and represent the directions Ali should move in each location to avoid hazards (up, down, left, and right, respectively). The $$$j$$$th character in the $$$i$$$th line gives the direction Ali should move when in row $$$i$$$ and column $$$j$$$ of the maze.

Output a single integer giving the number of unordered pairs of locations $$$(a, b)$$$ such that $$$a \neq b$$$, Ali will eventually reach $$$a$$$ starting at location $$$b$$$, and Ali will eventually reach $$$b$$$ starting at location $$$a$$$.

2 2
>v
^<

6

2 2
>v
^^

1

In the first test case, all points are reachable starting from any point, so all $$$6$$$ unordered pairs of distinct locations are valid.

In the second test case, the only valid pair is the first row and second column and the second row and second column.