java - 如何找到矩阵中的最短路径

Question

我有一道JAVA题，想了很久也解决不了:有一个矩阵，我需要找到从 Mat[0][0] 到矩阵右下角的最短路径，如果其中的数字大于，我只能继续到相邻的正方形(没有对角线)我现在正在使用的那个。

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}

所以一个有效的解决方案是:(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)

并且该方法将返回 14，因为这是最短的可能路径。

我必须只使用递归方法(没有循环)。

这是我到目前为止想出的，但我不知道如何找出哪个是最短的。

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;
}

我不确定这是否是这样做的方式，如果是:我怎么知道哪条是最短的方式，因为现在它会返回所有可能的方式并将它们加在一起(我认为)。另外，我想我应该添加一些关于到达矩阵右下角的内容。

代码不要太复杂。

Answer 1

我不确定转到下一个最小值的方法是否最短，但无论如何:

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;
    }
}

输出:

(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