Plumber

Our favourite plumber is on his way to save the princess located in the castle. The castle is represented by a 2-D grid that contains obstacles(denoted by a 'x') and coins(denoted by a 'c'). Empty squares in the castle will be denote by a '.'. Our plumber will always start at position (0, 0) in the grid and the princess will always be at position (r - 1, c - 1) in the grid where r and c denote the number of rows and columns in the grid respectively. Whilst on his way to save the princess what is the maximal number of coins that can be obtained?

An additional restriction is that our plumber can only move down, right and left but never up.

Additionally, the plumber cannot cross through the obstacles.

It is guaranteed that the starting locations of the plumber and the princess will not contain coins nor obstacles.

NOTE: the input will be a series of strings that will represent the grid.

Input

  • grid: Grid containing the castle layout

Output

Integer representing the maximal number of coins that can be obtained

Examples

Example 1:

Input:

grid = ["..", "cc"]

Output: 2

Explanation:

Both of the coins can be collected on the way to the princess

Example 2:

Input:

grid = ["..c", "..x", "..."]

Output: 1

Explanation:

After getting the coin in the first row, the plumber can move to the left and down to avoid the obstacle.

Constraints

  • 1 <= rows * columns <= 2000

Try it yourself

Solution

Title

Script

Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book.

Contrary to popular belief, Lorem Ipsum is not simply random text.

  >>> a = [1, 2, 3]
  >>> a[-1]
  3

Get premium for instant access to all content and solutions

Upgrade