{"id":"e69386b5-c9c6-4546-9eaf-eb36898a1c2d","name":"Print All Paths With Minimum Cost","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 maze.\r\n4. You are standing in top-left cell and are required to move to bottom-right cell.\r\n5. You are allowed to move 1 cell right (h move) or 1 cell down (v move) in 1 motion.\r\n6. Each cell has a value that will have to be paid to enter that cell (even for the top-left and bottom-right cell).\r\n7. You are required to traverse through the matrix and print the cost of the path which is least costly.\r\n8. Also, you have to print all the paths with minimum cost.","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\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":"23\r\nHVVHHVHVHV\r\nHVVHHVHHVV\r\n","questionVideo":"https://www.youtube.com/embed/f8Vdifn2YjQ?end=62","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":"ea27c7df-c690-4210-ae0f-103b0eacaa4f","name":"Print All Paths With Minimum Cost","slug":"print-all-paths-with-minimum-cost","type":1}],"next":{"id":"6223047d-e2b5-4a99-8fc2-e922814605b5","name":"Print all paths with minimum cost MCQ","type":0,"slug":"print-all-paths-with-minimum-cost-mcq"},"prev":null}}

Print All Paths With Minimum Cost

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 maze. 4. You are standing in top-left cell and are required to move to bottom-right cell. 5. You are allowed to move 1 cell right (h move) or 1 cell down (v move) in 1 motion. 6. Each cell has a value that will have to be paid to enter that cell (even for the top-left and bottom-right cell). 7. You are required to traverse through the matrix and print the cost of the path which is least costly. 8. Also, you have to print all the paths with minimum cost.

{"id":"e69386b5-c9c6-4546-9eaf-eb36898a1c2d","name":"Print All Paths With Minimum Cost","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 maze.\r\n4. You are standing in top-left cell and are required to move to bottom-right cell.\r\n5. You are allowed to move 1 cell right (h move) or 1 cell down (v move) in 1 motion.\r\n6. Each cell has a value that will have to be paid to enter that cell (even for the top-left and bottom-right cell).\r\n7. You are required to traverse through the matrix and print the cost of the path which is least costly.\r\n8. Also, you have to print all the paths with minimum cost.","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\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":"23\r\nHVVHHVHVHV\r\nHVVHHVHHVV\r\n","questionVideo":"https://www.youtube.com/embed/f8Vdifn2YjQ?end=62","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":"ea27c7df-c690-4210-ae0f-103b0eacaa4f","name":"Print All Paths With Minimum Cost","slug":"print-all-paths-with-minimum-cost","type":1}],"next":{"id":"6223047d-e2b5-4a99-8fc2-e922814605b5","name":"Print all paths with minimum cost MCQ","type":0,"slug":"print-all-paths-with-minimum-cost-mcq"},"prev":null}}
plane

Editor

Loading...

Print All Paths With Minimum Cost

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 maze. 4. You are standing in top-left cell and are required to move to bottom-right cell. 5. You are allowed to move 1 cell right (h move) or 1 cell down (v move) in 1 motion. 6. Each cell has a value that will have to be paid to enter that cell (even for the top-left and bottom-right cell). 7. You are required to traverse through the matrix and print the cost of the path which is least costly. 8. Also, you have to print all the paths with minimum cost.

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

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

23 HVVHHVHVHV HVVHHVHHVV

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode