`{"id":"0e7a54db-8cc0-4ce1-b65e-8af04f8f5a36","name":"Print All Paths With Maximum Gold","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 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\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.\r\n8. Also, you have to print all paths with maximum gold.\r\n","inputFormat":"A number n\r\nA number m\r\ne11\r\ne12..\r\ne21\r\ne22..\r\n.. n * m number of elements","outputFormat":"Check the sample output and question video.","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":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n private static class Pair {\r\n String psf;\r\n int i;\r\n int j;\r\n\r\n public Pair(String psf, int i, int j) {\r\n this.psf = psf;\r\n this.i = i;\r\n this.j = j;\r\n }\r\n }\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n int n = Integer.parseInt(br.readLine());\r\n int m = Integer.parseInt(br.readLine());\r\n int[][] arr = new int[n][m];\r\n\r\n for (int i = 0; i < n; i++) {\r\n String str = br.readLine();\r\n for (int j = 0; j < m; j++) {\r\n arr[i][j] = Integer.parseInt(str.split(\" \")[j]);\r\n }\r\n }\r\n\r\n //write your code here\r\n }\r\n\r\n\r\n}"},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"medium","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\r\n4 d3 d1 d2 d3 d1 \r\n","questionVideo":"https://www.youtube.com/embed/mme6Tqj8tyY?end=237","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":"17378a88-558d-4fb7-8f39-4676f832f3e5","name":"Print All Paths With Maximum Gold","slug":"print-all-paths-with-maximum-gold","type":1}],"next":{"id":"e14e38b7-fc43-43bf-88a0-2312779e94f8","name":"print all paths with maximum gold MCQ","type":0,"slug":"print-all-paths-with-maximum-gold-mcq"},"prev":{"id":"fb4644c1-9f71-40df-a74e-eaffffb3248d","name":"Print All Paths With Minimum Cost","type":3,"slug":"print-all-paths-with-minimum-cost"}}}`

# Print All Paths With Maximum Gold

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). 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. 8. Also, you have to print all paths with maximum gold.

`{"id":"0e7a54db-8cc0-4ce1-b65e-8af04f8f5a36","name":"Print All Paths With Maximum Gold","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 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\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.\r\n8. Also, you have to print all paths with maximum gold.\r\n","inputFormat":"A number n\r\nA number m\r\ne11\r\ne12..\r\ne21\r\ne22..\r\n.. n * m number of elements","outputFormat":"Check the sample output and question video.","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":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n private static class Pair {\r\n String psf;\r\n int i;\r\n int j;\r\n\r\n public Pair(String psf, int i, int j) {\r\n this.psf = psf;\r\n this.i = i;\r\n this.j = j;\r\n }\r\n }\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n int n = Integer.parseInt(br.readLine());\r\n int m = Integer.parseInt(br.readLine());\r\n int[][] arr = new int[n][m];\r\n\r\n for (int i = 0; i < n; i++) {\r\n String str = br.readLine();\r\n for (int j = 0; j < m; j++) {\r\n arr[i][j] = Integer.parseInt(str.split(\" \")[j]);\r\n }\r\n }\r\n\r\n //write your code here\r\n }\r\n\r\n\r\n}"},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"medium","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\r\n4 d3 d1 d2 d3 d1 \r\n","questionVideo":"https://www.youtube.com/embed/mme6Tqj8tyY?end=237","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":"17378a88-558d-4fb7-8f39-4676f832f3e5","name":"Print All Paths With Maximum Gold","slug":"print-all-paths-with-maximum-gold","type":1}],"next":{"id":"e14e38b7-fc43-43bf-88a0-2312779e94f8","name":"print all paths with maximum gold MCQ","type":0,"slug":"print-all-paths-with-maximum-gold-mcq"},"prev":{"id":"fb4644c1-9f71-40df-a74e-eaffffb3248d","name":"Print All Paths With Minimum Cost","type":3,"slug":"print-all-paths-with-minimum-cost"}}}` Editor

# Print All Paths With Maximum Gold

medium

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). 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. 8. Also, you have to print all paths with maximum gold.

## 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

Check the sample output and question video.

## Example

Sample Input

```.css-23h8hz{color:inherit;font-size:0.875rem;line-height:1.125rem;letter-spacing:0.016rem;font-weight:var(--chakra-fontWeights-normal);white-space:pre-wrap;}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

```.css-3oaykw{color:var(--chakra-colors-active-primary);font-size:0.875rem;line-height:1.125rem;letter-spacing:0.016rem;font-weight:var(--chakra-fontWeights-normal);white-space:pre-wrap;font-family:Monospace;}33 4 d3 d1 d2 d3 d1 ```

Question Video

Discussions

Show Discussion

Related Resources 