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:

Accenture Mock Quiz | Part 1

Question  1 Incorrect Marked out of 1.00 Remove flag Question text Select the true statement ? Select one: a.  Inheritance forms a is-a part of relationship between classes.   b.  Aggregation is the stronger form of Inheritance. c.  Aggregation forms the is-a type of relationship between classes. d.  Aggregation forms a is-a part of relationship between classes. Composition is the stronger form of Aggregation. Feedback The correct answer is: Aggregation forms a is-a part of relationship between classes. Composition is the stronger form of Aggregation. Question  2 Correct Marked out of 1.00 Flag question Question text What is the diagram that depicts the interaction between objects by arranging the objects in time sequence ? Select one: a.  Use Case Diagram b.  Sequence Diagram   c.  Component Diagram d.  Activity Diagram Feedback The correct answer is: Sequence Diagram Question  3 Incorrect Marked out of 1.00 Flag question...

Coin Change Combination

1. You are given a number n, representing the count of coins. 2. You are given n numbers, representing the denominations of n coins. 3. You are given a number "amt". 4. You are required to calculate and print the number of combinations of the n coins using which the       amount "amt" can be paid. Note 1: You have an infinite supply of each coin denomination i.e. same coin denomination can be                    used for many installments in payment of "amt" Note 2: You are required to find the count of combinations and not permutations i.e.                   2 + 2 + 3 = 7 and 2 + 3 + 2 = 7 and 3 + 2 + 2 = 7 are different permutations of same                    combination. You should treat them as 1 and not 3. Input Format A number n n1 n2 .. n number of elements A number amt Output Format A number representing the count of ...

Programming using Java Hands On - Control Structures | Check for Leap Year

  Given a year, check if the year is leap year or not.  If yes, the output should be “Leap Year”.  Else output should be “Not a Leap Year”.  The input should be a positive four digit number.  Else,  the output should be “Invalid Year”. Sample Input  1 : Enter the Year 2016 Sample Output  1 : Leap Year Sample Input  2 : Enter the Year 2001 Sample Output  2 : Not a Leap Year Result Description Summary of tests *Note: All the test cases might not have same weightage +------------------------------+ | 12 tests run/12 tests passed | +------------------------------+

Climb Stairs With Minimum Moves

1. You are given a number n, representing the number of stairs in a staircase. 2. You are on the 0th step and are required to climb to the top. 3. You are given n numbers, where ith element's value represents - till how far from the step you       could jump to in a single move.  You can of-course fewer number of steps in the move. 4. You are required to print the number of minimum moves in which you can reach the top of       staircase. Note -> If there is no path through the staircase print null. Input Format A number n .. n more elements Output Format A number representing the number of ways to climb the stairs from 0 to top. Constraints 0 <= n <= 20 0 <= n1, n2, .. <= 20 Sample Input 10 3 3 0 2 1 2 4 2 0 0 Sample Output 4 Solution: import java.io.*; import java.util.*; public class Main {     public static void main(String[] args) throws Exception {         // write your code here    ...

Subscribe to Get's Answer by Email