Why the Rabbit Came to Information Island
Time limit1sMemory limit256 MB
A rabbit moves right, up-right, or down-right through a grid with walls, carrots, and side gates; maximize carrots collected before exiting a side gate.
- Level
Medium7 of 10
- Topics
- Dynamic programming, Implementation, Matrix, Prefix sum
- Solved
- No attempts yet
Problem
A rabbit has come to Information Island!
Information Island can be represented as a grid with N rows and M columns, and for some reason carrots lie scattered here and there. A rabbit has just entered through the main gate of Information Island. A fierce wolf is chasing it from the left, so the rabbit moves only in the →, ↘, ↗ directions. On its way out, the rabbit wants to pick up as many carrots as possible. The main gate is dangerous because of the wolf, so the rabbit must leave through a side gate, and to pick up a carrot the rabbit must pass through the position where that carrot is. When the rabbit arrives at some side gate, it does not have to escape through that gate; it may keep moving and escape through another side gate. How many carrots can the rabbit pick up?
The rabbit's movement is defined precisely as follows. Let the position at row r and column c of the grid be (r, c). When the rabbit's current position is (r, c), the positions it can reach in one move are (r+1, c+1), (r, c+1), and (r-1, c+1). It cannot move into a wall or outside the grid.
Input
The first line gives the grid dimensions N and M. The following N lines give the state of the grid. '.' is an empty space, '#' is a wall, 'R' is the rabbit, 'C' is a carrot, and 'O' is a side gate of Information Island. Exactly one 'R' is given, and there may be zero or more 'O's.
Output
Print the maximum number of carrots the rabbit can obtain while leaving Information Island. If it cannot leave Information Island, print -1.
Constraints
1 ≤ N,M ≤ 1000