{"id":"465f5e76-746f-4d4f-b2af-331b6d428bbb","name":"Min Cost In Maze Traversal","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- \r\n right cell).\r\n7. You are required to traverse through the matrix and print the cost of path which is least costly.","inputFormat":"A number n\r\nA number m\r\ne11\r\ne12..\r\ne21\r\ne22..\r\n.. n * m number of elements","outputFormat":"The cost of least costly path.","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 <iostream>\n#include <vector>\n\nusing namespace std;\n\n\n\nint minCost(int n, int m, vector<vector<int>> &arr, vector<vector<int>> &dp ){\n \n // write your code here\n \n return 0;\n \n}\n\nint main() {\n\n int n;\n int m;\n\n cin >> n >> m;\n \n vector<vector<int>> arr(n, vector<int>(m));\t\t\n\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));\t\t\n\n cout << minCost(n, m, arr, dp);\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, arr):\n dp = [[0 for c in range(m)] for r in range(n)]\n \n # write code here\n \n \n return 0\n\n\n# driver code\n\ndef main():\n n = int(input())\n m = int(input())\n \n arr = []\n \n for i in range(0,n):\n ar=[]\n l=input()\n for j in range(0,m):\n lst=l.split(\" \")\n val=int(lst[j])\n ar.append(val)\n arr.append(ar)\n \n \n \n print(fun(n, m, arr))\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":"23","questionVideo":"https://www.youtube.com/embed/D-0souJUBMU","hints":[],"associated":[{"id":"0a1f7c53-f946-4021-9baa-4227406d4055","name":"Dynamic Programming based","slug":"dynamic-programming-based","type":4},{"id":"4bd44614-4f20-4b10-b2ac-de323c86dc5a","name":"Dynamic Programming optimise","slug":"dynamic-programming-optimise","type":4},{"id":"4fb523b1-7eb6-447c-905c-9b933b16e7a8","name":"dimensions of dp array","slug":"dimensions-of-dp-array","type":4},{"id":"84d6c181-a284-4b03-bbe8-4cd30e350dc3","name":"Time Complexity of Min cost In Maze Traversal","slug":"time-complexity-of-min-cost-in-maze-traversal","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":"a3b6281c-20d6-4bc3-87fc-a88d93d6f1b4","name":"Min Cost In Maze Traversal","slug":"min-cost-in-maze-traversal","type":1}],"next":{"id":"84f8566c-55cd-4bad-a075-ca22e67032bc","name":"Min Cost In Maze Traversal","type":3,"slug":"min-cost-in-maze-traversal"},"prev":{"id":"e317eafe-fefd-4c0c-a04e-9a0f90975ec3","name":"Climb Stairs With Minimum Moves","type":3,"slug":"climb-stairs-with-minimum-moves"}}}

Min Cost In Maze Traversal

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 path which is least costly.

{"id":"465f5e76-746f-4d4f-b2af-331b6d428bbb","name":"Min Cost In Maze Traversal","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- \r\n right cell).\r\n7. You are required to traverse through the matrix and print the cost of path which is least costly.","inputFormat":"A number n\r\nA number m\r\ne11\r\ne12..\r\ne21\r\ne22..\r\n.. n * m number of elements","outputFormat":"The cost of least costly path.","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 <iostream>\n#include <vector>\n\nusing namespace std;\n\n\n\nint minCost(int n, int m, vector<vector<int>> &arr, vector<vector<int>> &dp ){\n \n // write your code here\n \n return 0;\n \n}\n\nint main() {\n\n int n;\n int m;\n\n cin >> n >> m;\n \n vector<vector<int>> arr(n, vector<int>(m));\t\t\n\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));\t\t\n\n cout << minCost(n, m, arr, dp);\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, arr):\n dp = [[0 for c in range(m)] for r in range(n)]\n \n # write code here\n \n \n return 0\n\n\n# driver code\n\ndef main():\n n = int(input())\n m = int(input())\n \n arr = []\n \n for i in range(0,n):\n ar=[]\n l=input()\n for j in range(0,m):\n lst=l.split(\" \")\n val=int(lst[j])\n ar.append(val)\n arr.append(ar)\n \n \n \n print(fun(n, m, arr))\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":"23","questionVideo":"https://www.youtube.com/embed/D-0souJUBMU","hints":[],"associated":[{"id":"0a1f7c53-f946-4021-9baa-4227406d4055","name":"Dynamic Programming based","slug":"dynamic-programming-based","type":4},{"id":"4bd44614-4f20-4b10-b2ac-de323c86dc5a","name":"Dynamic Programming optimise","slug":"dynamic-programming-optimise","type":4},{"id":"4fb523b1-7eb6-447c-905c-9b933b16e7a8","name":"dimensions of dp array","slug":"dimensions-of-dp-array","type":4},{"id":"84d6c181-a284-4b03-bbe8-4cd30e350dc3","name":"Time Complexity of Min cost In Maze Traversal","slug":"time-complexity-of-min-cost-in-maze-traversal","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":"a3b6281c-20d6-4bc3-87fc-a88d93d6f1b4","name":"Min Cost In Maze Traversal","slug":"min-cost-in-maze-traversal","type":1}],"next":{"id":"84f8566c-55cd-4bad-a075-ca22e67032bc","name":"Min Cost In Maze Traversal","type":3,"slug":"min-cost-in-maze-traversal"},"prev":{"id":"e317eafe-fefd-4c0c-a04e-9a0f90975ec3","name":"Climb Stairs With Minimum Moves","type":3,"slug":"climb-stairs-with-minimum-moves"}}}
plane

Editor

Loading...

Min Cost In Maze Traversal

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 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 path which is least costly.

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

The cost of least costly path.

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

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode