how to find the shortest path in a matrix

Question

I have a question in JAVA I can't solve no matter how long I try to think about the solution: There's a matrix and I need to find the shortest path possible to get from Mat[0][0] to the bottom right of the matrix and I can only proceed to the adjacent square (no diagonals) if the number in it is bigger than the one I'm on right now.

For example:
    0   1   2   3   4
0 { 5   13  2   5   2 
1   58  24  32  3   24 
2   2   7   33  1   7 
3   45  40  37  24  70
4   47  34  12  25  2 
5   52  56  68  76  100}

So a valid solution would be: (0,0)->(0,1)->(1,1)->(2,1)->(2,2)->(2,3)->(3,1)->(3,0)->(0,4)->(0,5)->(5,1)->(5,2)->(5,3)->(5,4)

And the method will return 14 because that's the shortest possible path.

I have to use a recursive method only (no loops).

This is what I came up with so far but I don't know how to figure out which is the shortest one.

Public static int shortestPath(int[][]mat)
{
    int length=0;
    int i=0;
    int j=0;
    shortestPath(mat, length, i, j);
}


Private static int shortestPath(int[][]math, int length, int i, int j)
{
    if((i==mat.length)||(j==mat[i].length))
        return length;
    if(shortestPath(mat, length, i+1, j) > shortestPath(mat, length, i, j))
        return length +1;
    if(shortestPath(mat, length, i, j+1) > shortestPath(mat, length, i, j))
        return length +1;
    if shortestPath(mat, length, i-1, j) > shortestPath(mat, length, i, j))
        return length +1;
    if shortestPath(mat, length, i, j-1) > shortestPath(mat, length, i, j))
        return length +1;
}

I'm not sure if that's the way to do it, and if it is: how do I know which is the shortest way, because right now it would return all possible ways and will add them together (I think). Also, I think I should add something about reaching the bottom right of the matrix.

The code shouldn't be too complicated.

Answer 1

im not sure if the approach of going to the next smallest value is the shortest, but anyway:

public class Pathfinder {

    private int[][] matrix;
    private int matrixLenghtI;
    private int matrixLenghtJ;

    public Pathfinder(int[][] matrix, int matrixLenghtI, int matrixLenghtJ) {
        this.matrix = matrix;
        this.matrixLenghtI = matrixLenghtI;
        this.matrixLenghtJ = matrixLenghtJ;
    }

    public static void main(String[] args) {

        int matrixLenghtI = 6;
        int matrixLenghtJ = 5;

        int[][] matrix1 = { { 3, 13, 15, 28, 30 }, { 40, 51, 52, 29, 30 }, { 28, 10, 53, 54, 54 },
                { 53, 12, 55, 53, 60 }, { 70, 62, 56, 20, 80 }, { 80, 81, 90, 95, 100 } };

        int[][] matrix2 = { { 5, 13, 2, 5, 2 }, { 58, 24, 32, 3, 24 }, { 2, 7, 33, 1, 7 }, { 45, 40, 37, 24, 70 },
                { 47, 34, 12, 25, 2 }, { 52, 56, 68, 76, 100 } };

        Pathfinder finder1 = new Pathfinder(matrix1, matrixLenghtI, matrixLenghtJ);
        finder1.run();

        Pathfinder finder2 = new Pathfinder(matrix2, matrixLenghtI, matrixLenghtJ);
        finder2.run();
    }

    private void run() {
        int i = 0;
        int j = 0;

        System.out.print("(" + i + "," + j + ")");
        System.out.println("\nLength: " + find(i, j));
    }

    private int find(int i, int j) {
        int value = matrix[i][j];
        int[] next = { i, j };

        int smallestNeighbour = 101;
        if (i > 0 && matrix[i - 1][j] > value) {
            smallestNeighbour = matrix[i - 1][j];
            next[0] = i - 1;
            next[1] = j;
        }
        if (j > 0 && matrix[i][j - 1] < smallestNeighbour && matrix[i][j - 1] > value) {
            smallestNeighbour = matrix[i][j - 1];
            next[0] = i;
            next[1] = j - 1;
        }
        if (i < matrixLenghtI - 1 && matrix[i + 1][j] < smallestNeighbour && matrix[i + 1][j] > value) {
            smallestNeighbour = matrix[i + 1][j];
            next[0] = i + 1;
            next[1] = j;
        }
        if (j < matrixLenghtJ - 1 && matrix[i][j + 1] < smallestNeighbour && matrix[i][j + 1] > value) {
            smallestNeighbour = matrix[i][j + 1];
            next[0] = i;
            next[1] = j + 1;
        }

        System.out.print("->(" + next[0] + "," + next[1] + ")");

        if (i == matrixLenghtI - 1 && j == matrixLenghtJ - 1)
            return 1;

        return find(next[0], next[1]) + 1;
    }
}

Output:

(0,0)->(0,1)->(0,2)->(0,3)->(1,3)->(1,4)->(2,4)->(3,4)->(4,4)->(5,4)->(5,4)
Length: 10
(0,0)->(0,1)->(1,1)->(1,2)->(2,2)->(3,2)->(3,1)->(3,0)->(4,0)->(5,0)->(5,1)->(5,2)->(5,3)->(5,4)->(5,4)
Length: 14