yes

58. Deadly Tag

Time Limit: 1 seconds

Memory Limit: 128 MB

Rating: 1500

Alice is playing a game of Tag with Bob, and Bob was faced with the choice of either getting tagged, or jumping into a pool with crocodiles. Bob decided to jump in. You are given an integer $N$ $(1 \le N \le 1000)$ and an $N \cdot N$ matrix of characters, consisting of ‘B’ for Bob’s starting cell, ‘G’ for the goal cell, ‘C’ for cells with crocodiles, ‘\$’ for any cells with money, and ‘O’ for any safe cells. Bob may enter cells marked with ‘B’, ‘G’, ‘\$’ and ‘O’, but if he enters a cell marked with ‘C’, he dies. When he enters a cell with ‘\$’, his balance increases by 1 dollar but the ‘\$’ cell immediately turns into a ‘O’ cell. He starts with 0 dollars. Output the maximum possible balance Bob can obtain, with his position ending at the goal cell. If he can’t reach the goal cell without dying, output ‘-1’.

The first line has integer $N$. The next $N$ lines contain information about the matrix describing the pool.

Output Bob's final balance if he can survive, or '-1' if he dies even while making optimal decisions.

Sample Input 1:
6
OOOGCC
OOOOOO
CCC$$C
COOO$O
$CCOOO
COOOOB

Sample Output 1:
3

Not available for this problem.

IanOJ Contest #1 (Div. 3) > Problem D