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:

Pyramid

/*  To Print  1    2   2    3   3   3    4   4   4   4    5   5   5   5   5    */ #include   <iostream> using   namespace   std ; int   main (){       #ifndef  ONLINE_JUDGE          freopen ( "../asset/input.txt" , "r" , stdin );          freopen ( "../asset/output.txt" , "w" , stdout );     #endif     // Code here!!      int   n ;  cin >> n ;      for ( int   i = 1 ; i <= n ; i ++){          for ( int   j = 1 ; j <=  i ; j ++){     ...

Pattern

/* To print:                 *                *   *            *   *   *        *   *   *   *    *   *   *   *   *    */ #include   <iostream> using   namespace   std ; int   main (){       #ifndef  ONLINE_JUDGE          freopen ( "../asset/input.txt" , "r" , stdin );          freopen ( "../asset/output.txt" , "w" , stdout );     #endif     // Code here!!      in...

Pattern

  /* To print Pattern:                     *                 *   *             *   *   *         *   *   *   *     *   *   *   *   * */ #include   <iostream> using   namespace   std ; int   main (){       #ifndef  ONLINE_JUDGE          freopen ( "../asset/input.txt" , "r" , stdin );          freopen ( "../asset/output.txt" , "w" , stdout );     #endif     //...

Data Formats ( XML & JSON ) XML AND JSON | Post-Quiz

  Question   1 Correct Mark 1.00 out of 1.00 Flag question Question text State True or False. JSON is data oriented and does not provide display capabilities. Select one: True   False Feedback The correct answer is 'True'. Question  2 Incorrect Mark 0.00 out of 1.00 Flag question Question text Which one of the following indicators define that either one of the child element must occur within the element? Select one: choice sequence      all any Feedback Your answer is incorrect. The correct answer is: choice Question  3 Correct Mark 1.00 out of 1.00 Flag question Question text JSON object value is accessed by using ________. Select one: dot(.) notation   star(*) notation colon(:) notation dollar($) notation Feedback Your answer is correct. The correct answer is: dot(.) notation Question  4 Correct Mark 1.00 out of 1.00 Flag question Question text Which of the following is a well formed XML document? Select one: <?xml version=”1.0...

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

RDBMS Data Definition Language Create | Mobile_specification table

  Write a query to  Mobile_specification table with constraints mentioned. Refer the below schema Result Description Summary of tests +------------------------------+ | 3 tests run / 3 test passed | +------------------------------+

Arrange Buildings

1. You are given a number n, which represents the length of a road. The road has n plots on it's each side. 2. The road is to be so planned that there should not be consecutive buildings on either side of the road. 3. You are required to find and print the number of ways in which the buildings can be built on both side of roads. Input Format A number n Output Format A number representing the number of ways in which the buildings can be built on both side of roads. Constraints 0 < n <= 45 Sample Input 6 Sample Output 441 Solution: import java.io.*; import java.util.*; public class Main{ public static void main(String[] args) throws Exception {     // write your code here     Scanner scn = new Scanner(System.in);     long n = scn.nextInt();     long ob = 1;     long os = 1;     for (int i = 2; i <= n; i++) {       long nb = os;       long ns = os + ob;       ob = nb;   ...

Data Formats ( XML & JSON ) XML AND JSON XML AND JSON | Quiz 1

Data Formats ( XML & JSON )  XML AND JSON  XML AND JSON Quiz 1  

Software Engineering Concepts Basics Of Testing Basics Of Testing | Quiz 2

Software Engineering Concepts  Basics Of Testing  Basics Of Testing Quiz 2

Subscribe to Get's Answer by Email