Mock CCC '23 1 S4 - Roger Says Yabe

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 1G

Problem type

Roger likes saying yabe. Some people think he might be trying to say eBay, but obviously, he's saying yabe.

Roger is going rafting. The terrain that Roger is going rafting on is an R \times C grid where each square either has water that is flowing in some direction, is land and is boring, or is land and is interesting.

Roger starts his rafting trip by choosing any square with water and putting his raft there. The raft will follow the direction of water and move to the cell directly in that direction. The trip stops when the raft either enters a land cell, a water cell twice, or exits the grid.

As Roger sits in the raft, he can visit a land square if the land square is orthogonally adjacent to any water cell that Roger's raft visits.

If Roger visits a land square that is interesting, he says yabe. He can only do this once per land square.

Determine the maximum number of times Roger can say yabe if he selects the starting point of the raft optimally.

Constraints

2 \le R, C \le 500

There is at least one cell with water.

In tests worth 5 marks, RC \le 2500.

Input Specification

The first line contains two integers, R and C.

Each of the next R lines contains one string of C characters from <v^>.#. The first four characters represent water cells flowing left, down, up, and right. . represents a boring land square. # represents an interesting land square.

Output Specification

Output the maximum number of times Roger can say yabe.

Sample Input

4 5
>v<<.
^<..#
#...#
.#>^#

Sample Output

2

Comments

There are no comments at the moment.