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 -1) and coins (denoted by 1). Empty squares in the castle are denoted by 0.

Our plumber will always start at the first row in the grid and the princess will always be at the last row in the grid. On the plumber's way to save the princess (reach any position in the last row), what is the maximal number of coins that can be obtained?

Restrictions:

  • The plumber can only move down, right, and left, but never up.
  • The plumber cannot move through the obstacles.

If the plumber cannot reach the last row, return -1.

Input

  • grid: Grid containing the castle layout

Output

Integer representing the maximal number of coins that can be obtained, return -1 if the plumber cannot reach the last row.

Examples

Example 1:

Input:

1grid = [[0, 0], [1, 1]]

Output: 2

Explanation:

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

Example 2:

Input:

1grid = [[0, 0, 1], [0, 0, -1], [0, 0, 0]]

Output: 1

Explanation:

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

Example 3:

Input:

1grid = [[1,0,-1,1,0,1],[1,-1,1,-1,1,-1],[0,0,-1,-1,1,1]]

Output: 5

Explanation:

See solution.

Constraints

  • 2 <= 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.

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

Get premium for instant access to all content and solutions

Upgrade