wip

84. Lost Control

Time Limit: 2 seconds

Memory Limit: 1024 MB

Rating: 1500

You are playing the original game of snake, where your snake will always be moving (there is no stopping). If an arrow key is pressed, the snake will change its direction (eg: if the up key is pressed the snake will move up). You are eager to play Snake, but you realised that some of your arrow keys are not working! After some testing, you find out that your down arrow key and your left arrow key are not working. The only working keys are the up arrow key and the right arrow key. This means your snake can only move up and move right. In the game of snake, you start at the bottom left corner. You want to eat as many apples as possible. You are given an integer $n$, side length of the square 2D grid. The game board of snakes is given to you as a 2D grid of size $n \cdot n$, where the character ‘o’ represents an apple and the character ‘.’ represents empty space (nothing). Determine the maximum number of apples you can eat by only moving up and right. Note: it is guaranteed that the starting position of the snake will not contain an apple.

The first line has integer $n$, followed by $n$ lines containing information about the 2D grid.

Output the maximum number of apples you can eat under the constraints, assuming optimal play.

Sample Input 1:
6
......
..oo..
....o.
.o....
..o...
......

Sample Output 1:
3


Sample Input 2:
6
..o.o.
....o.
o.....
o..o..
....oo
......

Sample Output 2:
4


Sample Input 3:
6
..o.o.
...o..
.o....
..oo..
.o..o.
...o..

Sample Output 3:
5

For the first sample case: https://ians.site/cdn/p84-img1.png

KL Coding Cup March 2023 > Snake > Problem 3