{"id":"dd88df0c-1dfc-48e5-9323-c543feeb24a8","name":"Cherry Pickup","description":"1. You are given a number N, which represents the rows and columns of a 2-D matrix.\r\n2. Matrix contains only three values - \r\n a. Cell is empty.\r\n b. Cell contains a cherry.\r\n c. Cell contains a thorn and you can not pass through this cell.\r\n3. You have to find the maximum number of cherries that you can collect following these rules :\r\n a. You have to start from (0,0) and travel till (N-1,N-1) by moving right or down, \r\n one step at a time.\r\n b. After reaching (N-1,N-1), you have to come back to (0,0) by moving left or up, \r\n one step at a time. \r\n\r\nNote -> If there is no valid path between the top-left cell and bottom-right cell, then no cherries can be collected.","inputFormat":"A number N\r\narr1\r\narr2... (N*N numbers).","outputFormat":"Check the sample output and question video.","constraints":"1 &lt;= N &lt;= 50\r\nCells can have only three values 0,1 and -1.","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n\tpublic static int Solution(int r1, int c1, int r2, int[][] arr, int[][][] dp) {\r\n\t\t//write your code here\r\n\r\n\t\treturn 0;\r\n\t}\r\n\tpublic static void main(String[] args) {\r\n\t\tScanner scn = new Scanner(System.in);\r\n\t\tint n = scn.nextInt();\r\n\t\tint[][] arr = new int[n][n];\r\n\t\tfor(int i = 0; i < n; i++){\r\n\t\t\tfor(int j = 0 ; j < n; j++){\r\n\t\t\t\tarr[i][j] = scn.nextInt();\r\n\t\t\t}\r\n\t\t}\r\n\t\tint ans = Math.max(0,Solution(0, 0, 0, arr, new int[n][n][n]));\r\n\t\tSystem.out.println(ans);\r\n\t}\r\n\r\n}"},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"3\r\n0 \r\n1 \r\n-1\r\n1 \r\n0\r\n-1\r\n1 \r\n1 \r\n1","sampleOutput":"5\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"5539a6e8-c8bf-4f04-805c-e43e9d20e72a","name":"Dynamic Programming For Intermediate","slug":"dynamic-programming-for-intermediate-408","type":0},{"id":"d588635d-8c2f-4a52-a03e-4aa165b4cf27","name":"Cherry Pickup","slug":"cherry-pickup","type":1}],"next":{"id":"07c6a880-629a-4ad8-b755-57436d393803","name":"CHERRY PICKUP MCQ","type":0,"slug":"cherry-pickup-mcq"},"prev":{"id":"aa8da00b-d6fa-44f5-b9d6-a7abd343efb1","name":"FLOOR TILING-2 MCQ","type":0,"slug":"floor-tiling-2-mcq"}}}

Cherry Pickup

1. You are given a number N, which represents the rows and columns of a 2-D matrix. 2. Matrix contains only three values - a. Cell is empty. b. Cell contains a cherry. c. Cell contains a thorn and you can not pass through this cell. 3. You have to find the maximum number of cherries that you can collect following these rules : a. You have to start from (0,0) and travel till (N-1,N-1) by moving right or down, one step at a time. b. After reaching (N-1,N-1), you have to come back to (0,0) by moving left or up, one step at a time. Note -> If there is no valid path between the top-left cell and bottom-right cell, then no cherries can be collected.

{"id":"dd88df0c-1dfc-48e5-9323-c543feeb24a8","name":"Cherry Pickup","description":"1. You are given a number N, which represents the rows and columns of a 2-D matrix.\r\n2. Matrix contains only three values - \r\n a. Cell is empty.\r\n b. Cell contains a cherry.\r\n c. Cell contains a thorn and you can not pass through this cell.\r\n3. You have to find the maximum number of cherries that you can collect following these rules :\r\n a. You have to start from (0,0) and travel till (N-1,N-1) by moving right or down, \r\n one step at a time.\r\n b. After reaching (N-1,N-1), you have to come back to (0,0) by moving left or up, \r\n one step at a time. \r\n\r\nNote -> If there is no valid path between the top-left cell and bottom-right cell, then no cherries can be collected.","inputFormat":"A number N\r\narr1\r\narr2... (N*N numbers).","outputFormat":"Check the sample output and question video.","constraints":"1 &lt;= N &lt;= 50\r\nCells can have only three values 0,1 and -1.","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n\tpublic static int Solution(int r1, int c1, int r2, int[][] arr, int[][][] dp) {\r\n\t\t//write your code here\r\n\r\n\t\treturn 0;\r\n\t}\r\n\tpublic static void main(String[] args) {\r\n\t\tScanner scn = new Scanner(System.in);\r\n\t\tint n = scn.nextInt();\r\n\t\tint[][] arr = new int[n][n];\r\n\t\tfor(int i = 0; i < n; i++){\r\n\t\t\tfor(int j = 0 ; j < n; j++){\r\n\t\t\t\tarr[i][j] = scn.nextInt();\r\n\t\t\t}\r\n\t\t}\r\n\t\tint ans = Math.max(0,Solution(0, 0, 0, arr, new int[n][n][n]));\r\n\t\tSystem.out.println(ans);\r\n\t}\r\n\r\n}"},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"3\r\n0 \r\n1 \r\n-1\r\n1 \r\n0\r\n-1\r\n1 \r\n1 \r\n1","sampleOutput":"5\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"5539a6e8-c8bf-4f04-805c-e43e9d20e72a","name":"Dynamic Programming For Intermediate","slug":"dynamic-programming-for-intermediate-408","type":0},{"id":"d588635d-8c2f-4a52-a03e-4aa165b4cf27","name":"Cherry Pickup","slug":"cherry-pickup","type":1}],"next":{"id":"07c6a880-629a-4ad8-b755-57436d393803","name":"CHERRY PICKUP MCQ","type":0,"slug":"cherry-pickup-mcq"},"prev":{"id":"aa8da00b-d6fa-44f5-b9d6-a7abd343efb1","name":"FLOOR TILING-2 MCQ","type":0,"slug":"floor-tiling-2-mcq"}}}
plane

Editor

Loading...

Cherry Pickup

hard

1. You are given a number N, which represents the rows and columns of a 2-D matrix. 2. Matrix contains only three values - a. Cell is empty. b. Cell contains a cherry. c. Cell contains a thorn and you can not pass through this cell. 3. You have to find the maximum number of cherries that you can collect following these rules : a. You have to start from (0,0) and travel till (N-1,N-1) by moving right or down, one step at a time. b. After reaching (N-1,N-1), you have to come back to (0,0) by moving left or up, one step at a time. Note -> If there is no valid path between the top-left cell and bottom-right cell, then no cherries can be collected.

Constraints

1 <= N <= 50 Cells can have only three values 0,1 and -1.

Format

Input

A number N arr1 arr2... (N*N numbers).

Output

Check the sample output and question video.

Example

Sample Input

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

Sample Output

5

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode