1. You will be given a grid of the park, which contains only: 0 (empty path), 1 (cherry), -1(thorn) 2. You need to traverse from top left corner to bottom right and after reaching there go back to top left, collecting maximum possible cherries 3. You can only move in two directions: right and down 4. Once you pass over a cherry spot, it'll be marked as empty as you'd have collected the cherry 5. You cannot go through a path that contains thorns 6. Return maximum possible cherries collected 7. Input and output is handled for you 8. It is a functional problem ,please do not modify main() NOTE: If there is no valid path from top left corner to bottom right, cherries CANNOT be collected
Input Format
Input is handled for you
Output Format
Output is handled for you
Constraints
Grid is an N by N 2D array 1 <= N <= 50. Assume that grid[0][0] and grid[N-1][N-1] are not -1.
Notice
Try First, Check Solution later
1. You should first read the question and watch the question video.2. Think of a solution approach, then try and submit the question on editor tab.3. We strongly advise you to watch the solution video for prescribed approach.Example
Input
4 4 0 1 -1 -1 1 0 1 0 0 1 1 0 -1 -1 1 1
Output
7