{"id":"80e5b653-1a4b-4171-9c63-5fcf25904211","name":"Goldmine","description":"1. You are given a number n, representing the number of rows.\r\n2. You are given a number m, representing the number of columns.\r\n3. You are given n*m numbers, representing elements of 2d array a, which represents a gold mine.\r\n4. You are standing in front of left wall and are supposed to dig to the right wall. You can start from \r\n any row in the left wall.\r\n5. You are allowed to move 1 cell right-up (d1), 1 cell right (d2) or 1 cell right-down(d3).\r\n\r\n<img src=\"http://pepcoding.com/resources/ojquestionresource/images/goldmine.JPEG\" alt=\"goldmine\" width=\"500px\">\r\n\r\n6. Each cell has a value that is the amount of gold available in the cell.\r\n7. You are required to identify the maximum amount of gold that can be dug out from the mine.","inputFormat":"A number n\r\nA number m\r\ne11\r\ne12..\r\ne21\r\ne22..\r\n.. n * m number of elements","outputFormat":"An integer representing Maximum gold available.","constraints":"1 &lt;= n &lt;= 10^2\r\n1 &lt;= m &lt;= 10^2\r\n0 &lt;= e1, e2, .. n * m elements &lt;= 1000","sampleCode":{"cpp":{"code":"#include <bits/stdc++.h>\n\nusing namespace std;\n\n\nint collectGold(int n, int m, vector<vector<int>>& arr, vector<vector<int>>& dp) {\n\n //write your code here\n\n \n return 0;\n}\n\n\n\nint main() {\n int n, m;\n cin >> n >> m;\n\n vector<vector<int>> arr(n, vector<int>(m, 0));\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < m; j++) {\n cin >> arr[i][j];\n }\n }\n\n vector<vector<int>> dp(n, vector<int>(m, 0));\n\n cout << collectGold(n, m, arr, dp);\n\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws Exception {\r\n // write your code here\r\n }\r\n\r\n}"},"python":{"code":"def fun(n, m, mine):\n dp = [ [0 for c in range(m)] for r in range(n) ]\n \n # write code here\n \n \n \n return 0\n\n\n\n\n\n# driver code\n\ndef main():\n n = int(input())\n m = int(input())\n \n mine = []\n \n for i in range(0, n):\n a = []\n l = input()\n for j in range(0, m):\n lst = l.split(\" \")\n val = int(lst[j])\n a.append(val)\n mine.append(a)\n \n\n print(fun(n, m, mine))\n \nif __name__ == \"__main__\":\n main("}},"points":10,"difficulty":"easy","sampleInput":"6\r\n6\r\n0 1 4 2 8 2\r\n4 3 6 5 0 4\r\n1 2 4 1 4 6\r\n2 0 7 3 2 2\r\n3 1 5 9 2 4\r\n2 7 0 8 5 1","sampleOutput":"33","questionVideo":"https://www.youtube.com/embed/5KdvH15NJjc","hints":[],"associated":[{"id":"64cd1120-2f7c-43bc-8000-b7f83e4ff400","name":"concept of Dynamic Programmng","slug":"concept-of-dynamic-programmng","type":4},{"id":"aaadaf49-10c5-4423-8b73-8ef56bc05eee","name":"cells in the storage","slug":"cells-in-the-storage","type":4},{"id":"bb5bb0c6-7cba-4186-809c-4564a3a2569d","name":"DP optimizes the solution by taking advantage of which of the following:","slug":"dp-optimizes-the-solution-by-taking-advantage-of-which-of-the-following","type":4}],"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":"52d62581-1313-45fb-aaf0-1d72a45f6a50","name":"Dynamic Programming And Greedy For Beginners","slug":"dynamic-programming-and-greedy-for-beginners","type":0},{"id":"2b4b76f4-43ed-42b1-a9a5-e2868a8fc2b7","name":"Goldmine","slug":"goldmine","type":1}],"next":{"id":"47b6a395-4fcf-439e-9dd1-206622dd8b34","name":"Goldmine","type":3,"slug":"goldmine"},"prev":{"id":"84f8566c-55cd-4bad-a075-ca22e67032bc","name":"Min Cost In Maze Traversal","type":3,"slug":"min-cost-in-maze-traversal"}}}

Goldmine

1. You are given a number n, representing the number of rows. 2. You are given a number m, representing the number of columns. 3. You are given n*m numbers, representing elements of 2d array a, which represents a gold mine. 4. You are standing in front of left wall and are supposed to dig to the right wall. You can start from any row in the left wall. 5. You are allowed to move 1 cell right-up (d1), 1 cell right (d2) or 1 cell right-down(d3). <img src="http://pepcoding.com/resources/ojquestionresource/images/goldmine.JPEG" alt="goldmine" width="500px"> 6. Each cell has a value that is the amount of gold available in the cell. 7. You are required to identify the maximum amount of gold that can be dug out from the mine.

{"id":"80e5b653-1a4b-4171-9c63-5fcf25904211","name":"Goldmine","description":"1. You are given a number n, representing the number of rows.\r\n2. You are given a number m, representing the number of columns.\r\n3. You are given n*m numbers, representing elements of 2d array a, which represents a gold mine.\r\n4. You are standing in front of left wall and are supposed to dig to the right wall. You can start from \r\n any row in the left wall.\r\n5. You are allowed to move 1 cell right-up (d1), 1 cell right (d2) or 1 cell right-down(d3).\r\n\r\n<img src=\"http://pepcoding.com/resources/ojquestionresource/images/goldmine.JPEG\" alt=\"goldmine\" width=\"500px\">\r\n\r\n6. Each cell has a value that is the amount of gold available in the cell.\r\n7. You are required to identify the maximum amount of gold that can be dug out from the mine.","inputFormat":"A number n\r\nA number m\r\ne11\r\ne12..\r\ne21\r\ne22..\r\n.. n * m number of elements","outputFormat":"An integer representing Maximum gold available.","constraints":"1 &lt;= n &lt;= 10^2\r\n1 &lt;= m &lt;= 10^2\r\n0 &lt;= e1, e2, .. n * m elements &lt;= 1000","sampleCode":{"cpp":{"code":"#include <bits/stdc++.h>\n\nusing namespace std;\n\n\nint collectGold(int n, int m, vector<vector<int>>& arr, vector<vector<int>>& dp) {\n\n //write your code here\n\n \n return 0;\n}\n\n\n\nint main() {\n int n, m;\n cin >> n >> m;\n\n vector<vector<int>> arr(n, vector<int>(m, 0));\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < m; j++) {\n cin >> arr[i][j];\n }\n }\n\n vector<vector<int>> dp(n, vector<int>(m, 0));\n\n cout << collectGold(n, m, arr, dp);\n\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws Exception {\r\n // write your code here\r\n }\r\n\r\n}"},"python":{"code":"def fun(n, m, mine):\n dp = [ [0 for c in range(m)] for r in range(n) ]\n \n # write code here\n \n \n \n return 0\n\n\n\n\n\n# driver code\n\ndef main():\n n = int(input())\n m = int(input())\n \n mine = []\n \n for i in range(0, n):\n a = []\n l = input()\n for j in range(0, m):\n lst = l.split(\" \")\n val = int(lst[j])\n a.append(val)\n mine.append(a)\n \n\n print(fun(n, m, mine))\n \nif __name__ == \"__main__\":\n main("}},"points":10,"difficulty":"easy","sampleInput":"6\r\n6\r\n0 1 4 2 8 2\r\n4 3 6 5 0 4\r\n1 2 4 1 4 6\r\n2 0 7 3 2 2\r\n3 1 5 9 2 4\r\n2 7 0 8 5 1","sampleOutput":"33","questionVideo":"https://www.youtube.com/embed/5KdvH15NJjc","hints":[],"associated":[{"id":"64cd1120-2f7c-43bc-8000-b7f83e4ff400","name":"concept of Dynamic Programmng","slug":"concept-of-dynamic-programmng","type":4},{"id":"aaadaf49-10c5-4423-8b73-8ef56bc05eee","name":"cells in the storage","slug":"cells-in-the-storage","type":4},{"id":"bb5bb0c6-7cba-4186-809c-4564a3a2569d","name":"DP optimizes the solution by taking advantage of which of the following:","slug":"dp-optimizes-the-solution-by-taking-advantage-of-which-of-the-following","type":4}],"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":"52d62581-1313-45fb-aaf0-1d72a45f6a50","name":"Dynamic Programming And Greedy For Beginners","slug":"dynamic-programming-and-greedy-for-beginners","type":0},{"id":"2b4b76f4-43ed-42b1-a9a5-e2868a8fc2b7","name":"Goldmine","slug":"goldmine","type":1}],"next":{"id":"47b6a395-4fcf-439e-9dd1-206622dd8b34","name":"Goldmine","type":3,"slug":"goldmine"},"prev":{"id":"84f8566c-55cd-4bad-a075-ca22e67032bc","name":"Min Cost In Maze Traversal","type":3,"slug":"min-cost-in-maze-traversal"}}}
plane

Editor

Loading...

Goldmine

easy

1. You are given a number n, representing the number of rows. 2. You are given a number m, representing the number of columns. 3. You are given n*m numbers, representing elements of 2d array a, which represents a gold mine. 4. You are standing in front of left wall and are supposed to dig to the right wall. You can start from any row in the left wall. 5. You are allowed to move 1 cell right-up (d1), 1 cell right (d2) or 1 cell right-down(d3). goldmine 6. Each cell has a value that is the amount of gold available in the cell. 7. You are required to identify the maximum amount of gold that can be dug out from the mine.

Constraints

1 <= n <= 10^2 1 <= m <= 10^2 0 <= e1, e2, .. n * m elements <= 1000

Format

Input

A number n A number m e11 e12.. e21 e22.. .. n * m number of elements

Output

An integer representing Maximum gold available.

Example

Sample Input

6 6 0 1 4 2 8 2 4 3 6 5 0 4 1 2 4 1 4 6 2 0 7 3 2 2 3 1 5 9 2 4 2 7 0 8 5 1

Sample Output

33

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode