allcoding1_official

10Q) Ans

👍2

4.03K views06:50

11Q) Bob was walking his dog in the village.

Unfortunately he got lost in an orange grove and wants to reach the exit.
The grove can be represented as a 2D grid consisting of N rows and M columns such that

• The rows are number from 1 to N from top to down.

The columns are numbered from 1 to M from left to right.

Each cell (i, j) of the grid has either of the following

• An orange tree with A[i][j] oranges.

• An infinite number of lanterns.

It is given that cells with lanterns will be have value 0.
the beginning, Bob is at cell (1, 1) and he wants to reach the exit at cell (N, M). He can move either right or down in the grove. As Bob reaches a cell (i, j), he will eat some amount of oranges from the tree in that cell (at most A[i][j]). In case this cell has lanterns, he will not be able to eat any oranges.

Bob wants to mark the path he's following with lanterns, so when he reaches a cell he will send his dog to some cell which has lanterns then the dog will pick up a lantern and comeback to Bob to put the lantern in that cell

The dog can move up, down, left and right in the grid, and the dog travels 1 kilo meter when moving from one cell to another.

When Bob moves from one cell to another, his dog will follow him as well.

Bob defines the profit of a path that leads him to
the exit as the difference between the total amount
of oranges he could eat along that path and theof oranges he could eat along that path and the total distance in kilo meters his dog traveled along that path

Find the maximum profit of a path that leads Bob to the exit of the grove

The distance the dog travels with Bob when Bob moves from cell to another is not included (only the distance of getting lanterns is calculated for the dog)

• Bob will put lanterns in every cell of the path, including the starting and ending cells.

He can also move to a cell which has lanterns, but this will not affect the amount of oranges.

It is guaranteed that there is at least one cell with lanterns.
Input Format

The first line contains an integer, N, denoting the number of rows in Grid.

The next line contains an integer, M, denoting the number of columns in Grid.

Each line i of the N subsequent lines (where 0≤i< N) contains M space separated integers each describing the row Grid[i].
Constraints

1 <= N <= 10^5

1 <= M <= 10^5

0 <= Grid[i][j] <= 10^9
Sample Test Cases

Case 1

Input:

1

1

0

Output:

0

Explanation:

N=1, M-1, Grid=0

Bob is already at the ending cell, bob will not eat oranges and the dog will not travel anywhere since this cell has lanterns.

So the answer is 0.
Output:

2

Explanation:

N-2, M-2, Grid-[[3,0], [5,2]]

In the beginning, Bob will eat 3 oranges at cell (1, 1) then he will send his dog to cell (1, 2) to get a lantern, the dog will travel 2kms back and forth.

Then Bob will move with dog to cell (2, 1), eat 5 oranges and send his dog to cell (1, 2) again, the dog will travel 4kms (2kms for going and 2 for returning).

Finally Bob will move with the dog to the exit cell (2, 2), eat 2 oranges and send his dog to cell (1, 2), the dog will travel 2kms to get the lantern.

The final answer is 3-2 + 5-4 + 2-2 = 2.
Output:

3

Explanation:

N-3, M-3, Grid=[[5,4,0], [1,1,1], [6,5,0]]

Bob will take the path (1, 1), (1, 2), (2, 2), (3, 2), (3, 3) with profit: 5-4 + 4-2 + 1-4 + 5-2 +0 = 3

In cells (1, 1), (1, 2) Bob will send his dog to cell (1, 3) to get the lanterns.

In the remaining cells he will send the dog to cell (3, 3).

👍5❤1

5.7K views07:03