finding the lowest value in two dimensional array

Question

Program that reads a two-dimensional 10 by 10 array of random doubles in the range [0.0,100.0] from a file.Your program will find the minimum route value from the upper left corner of the array[0][0] to the lower right corner of the array[9][9] by following the next algorithm:

1. Starting at (0,0), you can move only right or down from your current position. The element (0,1) is your right. The element at (1,0) is your down.

2. Find the minimum of those two elements and and move there. By "move there" the meaning is that it will be your new position.

3. Add the minimum value to an accumulator. Keep record of your new position.

4. Look again at the values right and down from your current position.

5. Find the minimum of those two and move there. Keep adding your minimum value to the accumulator.

6. Keep repeating steps 4) and 5) until some of the following happens:

   • If your current row is the last one, you are not allowed to move down anymore. Your only choice is to move to the right.

   • If your current column is the last one, you are not allowed to move to the right anymore, your only choice is going down.

7.If you are at the last column and the last row, you have reached the end of the array and the program ends and displays:

• The total accumulated value.-The total number of moves that you have complete going from (0,0) to (9,9)

I am stuck at the loop that prints the X every time at the lowest value This is what I have so far. I am reading a file contents into an array

public static void main(String[] args) {
    File file=new File("D:\\routes.txt");
    Scanner inputFile= new Scanner(file);

    int rows=inputFile.nextInt();
    int columns=inputFile.nextInt();

    double [][] array= new double [rows][columns];
    double lowest=array[0][0];

    for(int row=0; row <rows; row++ )
    {                
        for(int col=0; col<rows; col++)
        {
            array[row][col] =inputFile.nextDouble();
        }
    }

    printMatrix(array);   
    printPosition(array,rows,columns);
}

public static void printMatrix(double[][] M)
{
    for (int row=0; row<M.length; row++)
    {
        for(int col=0; col<M[row].length; col++)
            System.out.printf("%7.2f  ", M[row][col]);
                    System.out.println();
    }
     System.out.println();
     System.out.println();   
}

public static void printPosition(double [][]M,int y , int x)
{
    for (int row=0; row<M.length; row++)
    {
        for (int col=0; col<M[row].length;col++)
            if (col==x && row==y)
                System.out.printf("%s","  X   ");
            else
                System.out.printf("%7.2f  ",M[row][col]);
        System.out.println();
    }
    System.out.println();
    System.out.println();
}

Answer 1

Your question lacks clarification. Anyway, assuming from a cell I can go only right and down. And route value is total cost of a path from starting cell to destination cell, need to minimize this route value. Also needs to print the path which is responsible for the minimum route value.

If this is what you are looking for then you can solve this very easily. Lets declare an array:

 dp[row][col], dp[i][j] [0 <= i < row, 0 <= j < col] //will hold the minimum route value from (0, 0) to (i, j). 

Then dp[row - 1][col - 1] will be the optimal route value. You can go to (i, j) only from (i - 1, j) or (i, j - 1) considering these positions are valid.

So, dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + array[row][col], you need to handle the cases when i - 1 or j - 1 becomes less than 0. To print the path you need to save some information for a cell. For (i, j) you need to save from which cell you have come to this cell.

Now you need to print the path. Start with the destination cell, you already know from which cell you have come to it, go to that cell and same logic applies until you reach the starting cell. Now you know the path but in reverse order, just print it in reverse order.

Answer 2

public static void pathFromPoint(double [][]M,int r , int c)
{
    double max = 101.0;
    int x,y;
    if (r-1>=0 && M[r-1][c]!=-1 && M[r-1][c]<max)
    {
        max = M[r-1][c];
        x=r-1;y=c;
    }
    .
    .
    .
    // Do the same for r+1,c and r,c-1 and r,c+1
    // Finally set the value of element (x,y) in the array as -1.0
    // Call pathFromPoint again with the array and x,y as r,c
    // check if r-1,r+1,c-1,c+1 is not out of the array range.
    // If you find no max, that is, if max remains as 101, just do return;
    System.out.println();
    System.out.println();
}