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:

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

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

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 ++){     ...

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

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

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

  Feedback Congratulations!! You have passed by securing more than 80% Question  1 Correct Mark 1.00 out of 1.00 Flag question Question text What is the correct syntax in HTML for creating a link on a webpage? Select one: <link src="mcqsets.html"> <a href="mcqsets.html">   <a src="mcqsets.html"> <body link="mcqsets.html"> Feedback Your answer is correct. The correct answer is: <a href="mcqsets.html"> Question  2 Correct Mark 1.00 out of 1.00 Flag question Question text What are the new features in HTML5? Select one: All of these   Canvas element is provided for 2D drawing Better support for local storage Video and audio elements are available for media playbacK New form controls like calendar, date, time, email, URL, search  Feedback Your answer is correct. The correct answer is: All of these Question  3 Correct Mark 1.00 out of 1.00 Flag question Question text ____________ is the HTML5 attribute that speci...

Data Formats ( XML & JSON ) XML AND JSON | Generate XSD For Mobile Store

  Generate XSD For Mobile Store <?xml version="1.0" encoding="UTF-8"?> <mobilestore> <mobile> <brand>Nokia</brand> <os>Symbian</os> <model>C6</model> <ram>1gb</ram> <internal>8gb</internal> </mobile> <mobile> <brand>Samsung</brand> <os>Android</os> <model>Galaxy</model> <ram>2gb</ram> <internal>8gb</internal> </mobile> <mobile> <brand>Sony</brand> <os>Android</os> <model>Experia</model> <ram>512mb</ram> <internal>16gb</internal> </mobile> </mobilestore> <? xml  version = "1.0"  encoding = "UTF-8" ?> < xs:schema   xmlns:xs = "http://www.w3.org/2001/XMLSchema"   elementFormDefault = "qualified"   attributeFormDefault = "unqualifi...

Subscribe to Get's Answer by Email