Apple Pickup

Hard
0/120
Average time to solve is 15m
9 upvotes
Asked in companies
Disney + HotstarFlipkart limitedCiena

Problem statement

Alice always loves to visit her garden and collect apples. The garden can be represented in the form of ‘N’ * ’N’ grid say ‘MATRIX’, where each cell of the grid can have one of the possible values:

1 -> The cell contains an apple that Alice can pick up and pass through it.

-1 -> The cell contains a bush and Alice can not visit this cell.

0 -> The cell is empty and Alice can pass through it.

Alice is present at the top left corner of the matrix or we can say at point (0,0).

Alice has to reach the bottom right corner of the matrix (‘N’-1,’N’-1) and return back to the starting point (0,0).

1. After picking an apple the cell will become empty.

2. While going towards the bottom right corner, Alice can either move Right or Down at each step.

3. While going towards the top left corner, Alice can either move Left or Up at each step.

4. If there is no path from (0,0) to (‘N’-1, ‘N’-1) then Alice will not pick any apple.

Your task is to help Alice to collect the maximum number of apples during her journey.

For example:

If the given matrix is :
[1, 1, -1, 1]
[1, 0, 1, 1]
[1, 1, 0, 1]
[0, -1, -1, 1]

One of the possible ways to collect maximum apples is :

Path for going towards bottom right corner: 
(0,0) -> (0,1) -> (1,1) -> (1,2) -> (1,3) -> (2,3) -> (3,3)

Apples collected are equal to 6.

Path for going towards top left corner:
(3,3) -> (2,3) ->(2,2) -> (2,1) -> (2,0) -> (1,0) -> (0,0)

Apples collected are equal to 3.

So Alice can collect a maximum of 9 apples.
Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first line of each test case contains a space-separated integer ‘N’ representing the number of rows and columns. 

The next ‘N’ lines of each test case contain ‘N’ single space-separated integers denoting the values of ‘MATRIX’.

Output format:

For each test case, print a single line containing a single integer representing the maximum number of apples Alice can collect.

The output of every test case will be printed in a separate line.

Note :

You don’t have to print anything, it has already been taken care of. Just implement the given function.

Constraints

1 <= T <=10
1 <= N <= 50
-1 <= MATRIX[i] <= 1

Where ‘T’ denotes the number of test cases, ‘N’ denotes the number of rows and columns of ‘MATRIX’.

Time limit: 1 sec.

Sample input 1:

1
3
1 -1 1
0 1 -1
1 -1 0

Sample output 1:

0

Explanation for sample input 1:

We can see there is no possible path to reach (2,2) from (0,0), so no apples will be collected.

Sample input 2:

2    
4
1 1 0 0 
0 1 0 1
1 1 0 0 
0 1 1 1
2
-1 -1
-1 -1

Sample output 2:

9
0

Explanation for sample input 2:

For the test case 1:
One of the possible way to collect 9 apples is :

Path for going towards bottom right corner: 
(0,0) -> (0,1) -> (1,1) -> (1,2) -> (1,3) -> (2,3) -> (3,3)

Apples collected are equal to 5.

Path forgoing towards top left corner:
(3,3) -> (3,2) ->(3,1) -> (2,1) -> (2,0) -> (1,0) -> (0,0)
Apples collected are equal to 4.

For the test case 2:
As Alice can not visit (0,0), so she will never be able to reach (‘N’-1,’N’-1).
Hint

Can you think of a solution that explores various paths simultaneously?

Approaches (3)
Recursion

 The idea is to explore two paths simultaneously from (0,0) to (‘N’-1, ‘N’-1) and collect maximum apples. However, while implementing this approach we may count 1 apple two times, so we need to take care of this problem.

 

Complete Algorithm:

  • We will make a helper recursive function named ‘SOLVE’ which will receive 3 parameters ‘R1’, ‘C1’, ‘C2’.
  • We will calculate ‘R2’ = ‘R1’+’C1’-’C2’,  (‘R1’+’C1’ ==  ‘R2’+’C2’) because at each step value of 1 variable is increased by 1 from both sides as each person will move 1 step.
  • Here (‘R1’, ‘C1’) will point to the current position for the first-person and (‘R2’,’ C2’)  will point to the current position for a second person. All 4 variables will be initialized to a large negative value(INT_MIN).
  • Base Case:
    • If  ‘R1’ == ‘N’ -1 and ‘C1’ == ‘N’ -1 then do:
      • Return ‘MATRIX[ R1][C1]’.
    • If ‘R2’ ==  ‘N’-1 and ‘C2’ ==  ‘N’-1 then do:
      • Return ‘MATRIX[ R2][C2]’.
    • If both people are standing on the same point (‘R1’==’R2’ and ‘C1’==’C2’) then do:
      • Return ‘MATRIX[ R2][C2]’.
    • Otherwise do:
      • Return ‘MATRIX[ R1][C1]’ +  ‘MATRIX[ R2][C2]’.

 

  • Recursive Calls:
    • Initialize an integer variable ‘ANS’=0.
    • Now 4 possible combinations can be made :
    • Let ‘DOWN_DOWN’ = Both person go to the Downside.
    • Let ‘RIGHT_DOWN’ =  the First-person goes to the Right side and second to the Downside.
    • Let ‘DOWN_RIGHT’ =  the First person goes to Downside and second to the Right side.
    • Let RIGHT_RIGHT = Both person go to Right side.
    • We can calculate the values of the above variable by making recursive calls.
      • DOWN_DOWN = SOLVE (R1+1, C1, R2+1, C2)
      • RIGHT_DOWN =  SOLVE (R1, C1+1, R2+1, C2)
      • DOWN_RIGHT = SOLVE (R1+1, C1, R2, C2+1)
      • RIGHT_RIGHT = SOLVE (R1, C1+1, R2, C2+1)
  • Set ‘ANS’  = ‘ANS’ + the maximum of these 4 variables.
  • Return ‘ANS’.
Time Complexity

O(4 ^ N), where ‘N’ is the number of rows and columns.

 

As during each call to function we are making further 4 calls thus making time complexity as O(4 ^ N).

Space Complexity

O(4 ^ N), where ‘N’ is the number of steps.

 

This is the space used by the recursion stack to store 4 ^ N calls.

Code Solution
(100% EXP penalty)
Apple Pickup
Full screen
Console