Skip to main content

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.

Input Format

A number n

A number m

e11

e12..

e21

e22..

.. n * m number of elements

Output Format

The cost of least costly path.


Constraints

1 <= n <= 10^2

1 <= m <= 10^2

0 <= e1, e2, .. n * m elements <= 1000

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


Solution:

import java.io.*;

import java.util.*;


public class Main {


    public static void main(String[] args) throws Exception {

        // write your code here

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int m = sc.nextInt();

        int[][] arr = new int[n][m];

        

        for(int i=0;i<n;i++)

            for(int j=0;j<m;j++)

                arr[i][j] = sc.nextInt();

        

        int[][] dp = new int[n][m];

        dp[n-1][m-1] = arr[n-1][m-1];

        for(int i=n-1;i>=0;i--){

            for(int j=m-1;j>=0;j--){

                // move down n right

                int min = Integer.MAX_VALUE;

                if(j+1 <m)

                    min = Math.min(min,dp[i][j+1]);

                if(i+1<n)    

                    min = Math.min(min,dp[i+1][j]);

                if(min == Integer.MAX_VALUE)    continue;

                    dp[i][j] = arr[i][j] + min;

            }

        }

        System.out.println(dp[0][0]);

    }

}

Comments

Must Read:

DFA Solutions

  Question  1 Correct Mark 1.00 out of 1.00 Flag question Question text To secure the http messages in the API calls, its necessary to: Select one: a. All the above b. Use cryptography c. implement identity management d. avoid hardcoding any sensitive data in the messages Feedback The correct answer is: All the above Question  2 Correct Mark 1.00 out of 1.00 Remove flag Question text A team has completed 10 Sprints and moving to the 11th Sprint. Till Sprint 10, the team has achieved an average of 50 story points per sprint. The same is projected as their velocity for the upcoming sprints with the Client. What is this approach called? Select one: a. Velocity Driven Sprint Planning b. Velocity Driven Commitment c. Commitment Driven Velocity d. Commitment Driven Sprint Planning Feedback The correct answer is: Velocity Driven Sprint Planning Question  3 Incorrect Mark 0.00 out of 1.00 Remove flag Question text Jack is grooming himself to be a potential Product Owner. Kno...

Subscribe to Get's Answer by Email