CODEWITHSUNDEEP
java
Sunjaree Ibn Zulfiker
Sunjaree Ibn Zulfiker

Reputation: 43

Minimum path sum in matrix

Given a matrix of N * M. Find the minimum path sum in matrix. The minimum path is sum of all elements from first row to last row where you are allowed to move only down or diagonally to left or right. You can start from any element in first row. I've written the code,but what is wrong in my code/logic? here in my algorithm I am starting from the element of the top row, now I'm going to the second row and algorithm is finding the minimum value and add with the first element and thus it makes way to the bottom(a element can only add with the elment which is under it and also can move diagonally right and left) 

import java.util.Scanner;
public class Main{


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int row, column, i, j,temp=0;
        System.out.print("Please enter the desire grid dimension: ");
        row = sc.nextInt();
        column = sc.nextInt();
        int array[][] = new int[row][column];
        System.out.println("Please enter the desired input:");

        for (i = 0; i < row; i++) {
            for (j = 0; j < column; j++) {

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

            }
        }


        for(i=1;i<row;i++){
            for(j=0;j<column;j++){

                array[i][j] += Math.min((j==0)?0:array[i-1][j-1],Math.min(array[i-1][j],(j==column-1)?0:array[i-1][j+1]));
            }
        }

for(i=0;i<row;i++){
   for(j=0;j<column;j++){
System.out.print(array[i][j] + " ");
}
System.out.println();
}



        for(j=0;j<column-1;j++){
            temp = Math.min(array[row-1][j],array[row-1][j+1]);
        }
        System.out.println(temp);

    }

}

let your input is

1  5  1  5  1*  5
3  3  2  3  3*  4
2  3  4  4  3   2*
2  2  3  2  2*  4
2  2  4  3  4   2*
4  4  4  4  2*  3

your output should be 12,path is marked with(*) 1+3+2+2+2+2=12

I'm getting 3,because after running my algorithm the matrix became

1 5 1 5 1 5 
3 4 3 4 4 4 
2 6 7 7 7 2 
2 4 9 9 4 4 
2 4 8 7 8 2 
4 6 8 11 4 3

Upvotes: 1

Views: 435

Answers (1)

Anonymous
Anonymous

Reputation: 86232

I am not giving you a complete answer. You will learn more from finding out yourself. At the same time this will be more gratifying for you. So I will just guide you slightly on the way and trust you to do the rest yourself. It’s not that hard.

First, however, for other readers to follow what I write I need to give the explanation that you should have given in the question of how your algorithm was supposed to work. You are modifying the matrix in a way so that each cell instead of its original number gets to contain the minimum sum of a path from the top to that cell inclusive. For example:

  • We see from your matrix after the algorithm has run that the top line is unchanged. This is correct since you can go directly into each cell, so the sum is equal to the original cell value.
  • In the second line, the second (index 1) cell has been changed from 3 to 4. This is correct since to go to that cell we need to go through 1 or 5 or 1 in the first line. 1 gives the minimal sum, so 1 is added to 3, hence 4.
  • In the same line, the leftmost cell is unchanged 3. The is incorrect. To get to this cell you also need to go through either 1 or 5 in the first line, so this 3 too should have been changed to 4. I will give you one piece of information: the cell was not forgotten. Your loop assigns a value to the cell, only not the correct value. 1 should have been added, instead 0 was added. Where does this 0 come from? Your turn! Happy debugging.

Upvotes: 1

Related Questions