logo标签列表

如何在矩阵中找到最短路径

javarecursionmatrixshortest-path
5

我有一个与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;
}

我不确定这是否是正确的方法，如果是：我如何知道哪条路线最短？因为现在它会返回所有可能的路线并将它们加在一起（我认为）。 另外，我认为我应该添加一些关于到达矩阵右下角的内容。

代码不应该太复杂。

你能向左和向上走吗，还是只能向下和向右走？ 你的递归基础情况是什么，何时停止？我可以看到两种情况，你会“底部输出”。 递归情况是什么？ - Paul Rubel
是的，你可以向上、向下、向右和向左移动。当我到达矩阵的边缘或者到达右下角时，我需要停止。你说的递归情况是什么意思？ - Uranus
我修改了矩阵的最短路径，使得问题更容易理解，而不是10。 - Uranus
2
Dijkstra的最短路径算法（Google，Wikipedia）应该适用于这里。 - JohnB
你可以先阅读https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm，理解它并自己实现伪代码。或者使用其他最短路径算法。 - Zabuzard
显示剩余3条评论
7个回答
1

我很喜欢这个问题。不幸的是，我已经多年没有用Java工作了，所以这个答案是伪代码，你需要修复一些语法错误。可能有些函数参数应该是引用而不是副本，你会弄清楚的（更新：下面我添加了一个Python版本的测试过的版本）。

// just a little thing to hold a set of coordinates
class Position 
{
    // not bothering with private / getters
    public int x ;
    public int y ;
    public constructor (int x, int y) 
    {
        this.x = x ;
        this.y = y ;
    }
}

class PathFinder
{
    public void main (void)
    {
        // create a path with just the start position
        start = new Position(0, 0) ;
        path = new Vector() ;
        path.add(start) ;
        // create an empty path to contain the final shortest path
        finalPath = new Vector() ;
        findPath(path, finalPath) ;
        print ("Shortest Path: ") ;
        showPath (finalPath) ;
    }

    private void showPath (Vector path) {
        // print out each position in the path
        iter = path.iterator() ;
        while (pos = iter.next()) {
            print ("(%, %) ", pos.x, pos.y);
        }
        // print out the length of the path
        print ("  Length: %\n", path.size()) ;
    }

    // recursive function to find shortest path
    private void findPath (Vector path, Vector finalPath)
    {
        // always display the current path (it should never be the same path twice)
        showPath(path) ;

        // where are we now?
        here = path.lastElement() ;

        // does the current path find the exit (position 4,5)?
        if (here.x == 4 && here.y == 5) {
            if (finalPath.size() == 0) {
                //finalPath is empty, put the current path in finalPath
                finalPath = path ;
            } else {
                // some other path found the exit already.  Which path is shorter?
                if (finalPath.size() > path.size()) {
                    finalPath = path ;
                }
            }
            // either way, we're at the exit and this path goes no further
            return ;
        }

        // path is not at exit; grope in all directions
        // note the code duplication in this section is unavoidable
        // because it may be necessary to start new paths in three
        // directions from any given position
        // If no new paths are available from the current position,
        // no new calls to findPath() will happen and 
        // the recursion will collapse.

        if (here.x > 0 && matrix[here.x-1][here.y] > matrix[here.x][here.y]) {
            // we can move left
            newPos = new Position(here.x-1, here.y) ;
            newPath = path ;
            newPath.add (newPos) ;
            findPath(newPath, finalPath) ;
        }

        if (here.x < 4 && matrix[here.x+1][here.y] > matrix[here.x][here.y]) {
            // we can move right
            newPos = new Position(here.x+1, here.y) ;
            newPath = path ;
            newPath.add (newPos) ;
            findPath(newPath, finalPath) ;
        }

        if (here.y > 0 && matrix[here.x][here.y-1] > matrix[here.x][here.y]) {
            // we can move up
            newPos = new Position(here.x, here.y-1) ;
            newPath = path ;
            newPath.add (newPos) ;
            findPath(newPath, finalPath) ;
        }

        if (here.y < 5 && matrix[here.x][here.y+1] > matrix[here.x][here.y]) {
            // we can move down
            newPos = new Position(here.x, here.y+1) ;
            newPath = path ;
            newPath.add (newPos) ;
            findPath(newPath, finalPath) ;
        }
    }
}

这是同一算法的Python测试版本。(我注意到使用x，y作为坐标有点误导人。x实际上是“垂直的”，而y是“水平的”，数组的索引方式是这样的。我设置了一个矩阵，有四条通往出口的路径和几个死胡同。)
import copy, sys

matrix = [
        [5,  13, 17, 58,   2], 
        [17, 24, 32,  3,  24],
        [23,  7, 33,  1,   7],
        [45, 40, 37, 38,  70],
        [47, 34, 12, 25,   2],
        [52, 56, 68, 76, 100]]

def showPath(path):
    for position in path:
        sys.stdout.write("(" + str(position[0]) + ", " + str(position[1]) + "), ")
    sys.stdout.write("\n\n")
    sys.stdout.flush()

def findPath(path):
    #showPath(path)
    global finalPath
    x = path[-1][0]
    y = path[-1][1]
    if x == 5 and y == 4:
        showPath(path)
        if len(finalPath) == 0 or len(finalPath) > len (path):
            finalPath[:] = copy.deepcopy(path)
        return
    if x > 0 and matrix[x-1][y] > matrix[x][y]:
        # we can move up
        newPath = copy.deepcopy(path)
        newPath.append([x-1, y])
        findPath(newPath)
    if x < 5 and matrix[x+1][y] > matrix[x][y]:
        # we can move down
        newPath = copy.deepcopy(path)
        newPath.append([x+1, y])
        findPath(newPath)
    if y > 0 and matrix[x][y-1] > matrix[x][y]:
        # we can move left
        newPath = copy.deepcopy(path)
        newPath.append([x, y-1])
        findPath(newPath)
    if y < 4 and matrix[x][y+1] > matrix[x][y]:
        # we can move right
        newPath = copy.deepcopy(path)
        newPath.append([x, y+1])
        findPath(newPath)

path = []
path.append([0, 0])
finalPath = []
findPath(path)
print "Shortest Path: " + str(len(finalPath)) + " steps.\n"
showPath(finalPath)

如果您取消注释findPath()中的第一个showPath（）调用，则可以查看每个步骤并查看哪些死路被丢弃。如果只显示到达出口的路径，则输出如下：
(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (5, 1), (5, 2), (5, 3), (5, 4), 
(0, 0), (1, 0), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (3, 0), (4, 0), (5, 0), (5, 1), (5, 2), (5, 3), (5, 4), 
(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), 
(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (3, 2), (3, 1), (3, 0), (4, 0), (5, 0), (5, 1), (5, 2), (5, 3), (5, 4), 
Shortest Path: 10 steps.
(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (5, 1), (5, 2), (5, 3), (5, 4),
1

位置类：

/**
 * Represents a position in the matrix.
 */
public class Position {

    final private int x;
    final private int y;

    public Position(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    @Override
    public String toString() {
        return "(" + x + ", " + y + ')';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Position position = (Position) o;

        if (x != position.x) return false;
        return y == position.y;

    }

    @Override
    public int hashCode() {
        int result = x;
        result = 31 * result + y;
        return result;
    }
}

Board类：

/**
 * A board represents all of the locations in the matrix.  It provides a simple interface to getting
 * the value in a position, and tracking the height and width of the matrix.
 */
public class Board {
    final int [][] board;

    public Board(int[][] board) {
        this.board = board;
    }

    final int positionValue(Position position) {
        return this.board[position.getY()][position.getX()];
    }

    final int getWidth() {
        return board[0].length;
    }

    final int getHeight() {
        return board.length;
    }
}

路径查找器类：
import java.util.ArrayList;
import java.util.List;

/**
 * Find the shortest path from a starting point to ending point in a matrix, assuming you can
 * only move to a position with a greater value than your current position.
 */
public class PathFinder {

    final private Board board;
    final private Position start;
    final private Position end;


    public PathFinder(Board board, int startX, int startY, int endX, int endY) {
        this.board = board;
        this.start = new Position(startX, startY);
        this.end = new Position(endX, endY);
    }

    /**
     * Gets the shortest path from the start to end positions.  This method
     * takes all of the paths, then determines which one is shortest and returns that.
     *
     * @return the shortest path from the start to end positions.
     */
    public List<Position> shortestPath() {

        List<List<Position>> allPaths = this.getAllPaths();

        System.out.println("Paths found: " + allPaths.size());
        List<Position> shortestPath = null;

        for (List<Position> path : allPaths) {
            if (shortestPath == null) {
                shortestPath = path;
            }
            else if (shortestPath.size() > path.size()) {
                shortestPath = path;
            }
        }

        return shortestPath;
    }

    /**
     * Convenience method for starting the getAllPaths process.
     *
     * @return all of the paths from the start to end positions
     */
    private List<List<Position>> getAllPaths() {
        List<List<Position>> paths = new ArrayList<List<Position>>();
        return this.getAllPaths(paths, new ArrayList<Position>(), start);
    }

    /**
     * Gets all of the paths from the start to end position.  This is   done recursively by visiting every
     * position, while following the rules that you can only move to a  position with a value greater
     * than the position you're currently on.  When reaching the end position, the path is added to
     * the list of all found paths, which is returned.
     *
     * @param paths the current list of all found paths.
     * @param path the current path
     * @param position the current position
     * @return all paths from the start to end positions
     */
    private List<List<Position>> getAllPaths(List<List<Position>> paths, List<Position> path, Position position) {
        path.add(position);
        if (position.equals(end)) {
            paths.add(path);
            return paths;
        }

        //x+
        if (position.getX() + 1 < board.getWidth()) {
            Position xp = new Position(position.getX() + 1, position.getY());
            if (board.positionValue(position) < board.positionValue(xp)) {
                getAllPaths(paths, new ArrayList<Position>(path), xp);
            }
        }
        //x-
        if (position.getX() - 1 >= 0) {
            Position xm = new Position(position.getX() - 1, position.getY());
            if (board.positionValue(position) < board.positionValue(xm)) {
                getAllPaths(paths, new ArrayList<Position>(path), xm);
            }
        }
        //y+
        if (position.getY() + 1 < board.getHeight()) {
            Position yp = new Position(position.getX(), position.getY() + 1);
            if (board.positionValue(position) < board.positionValue(yp)) {
                getAllPaths(paths, new ArrayList<Position>(path), yp);
            }
        }
        //y-
        if (position.getY() - 1 >= 0) {
            Position ym = new Position(position.getX(), position.getY() - 1);
            if (board.positionValue(position) < board.positionValue(ym)) {
                getAllPaths(paths, new ArrayList<Position>(path), ym);
            }
        }

        return paths;
    }

    /**
     * Run the example then print the results.
     *
     * @param args na
     */
    public static void main(String[] args) {
        int [][] array = {{5, 13, 2, 5, 2},
                            {14, 24, 32, 3, 24},
                            {15, 7, 33, 1, 7},
                            {45, 40, 37, 24, 70},
                            {47, 34, 12, 25, 2},
                            {52, 56, 68, 76, 100}
        };

        final Board board = new Board(array);
        final Position end = new Position(board.getWidth()-1, board.getHeight() - 1);
        final PathFinder pathFinder = new PathFinder(board, 0, 0, board.getWidth()-1, board.getHeight()-1);

        final List<Position> path = pathFinder.shortestPath();

        System.out.println("Shortest Path: ");
        for (Position position : path) {
            if (!position.equals(end)) {
                System.out.print(position + " -> ");
            }
            else {
                System.out.println(position);
            }
        }
        System.out.println();
    }
}
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
谢谢您的建议，但正如我所提到的，这需要是一个递归方法。 - Uranus
0
public class shortestPath{
public static int shortestPath(int[][] mat){
    if(mat == null || mat.length == 0 || mat[0].length == 0)
        return 0;
    else {
        int n = shortestPath(mat, 0, 0, 0);
        return (n == mat.length*mat.length+1 ) ? 0 : n;
    }
}

private static int shortestPath(int[][]mat, int row, int col,int prev){

    if (!valid(mat,row,col) || !(mat[row][col] > prev)){
        return mat.length*mat.length+1;
    } else if(row == mat.length - 1 && col == mat[row].length - 1) {
        return 1;
    } else {
        return minimum(shortestPath(mat,row-1,col, mat[row][col]), 
            shortestPath(mat,row+1,col, mat[row][col]),
            shortestPath(mat,row,col-1, mat[row][col]),
            shortestPath(mat,row,col+1, mat[row][col])) + 1;
    }
}

private static boolean valid(int[][]mat,int row, int col){
    if(row < 0 || col < 0 || col > mat[0].length-1 || row > mat.length-1)
        return false;
    else
        return true;
}

private static int minimum(int x, int y, int t, int z){
    int min1 = (x > y)? y : x;
    int min2 = (t > z)? z : t;

    return (min1 > min2)? min2 : min1;
}

public static void main(String[] args){

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

    System.out.println(shortestPath(maze));
}

}

0

在这里，你可以构建一棵树，列出所有可能性，然后选择最短路径。内部使用循环来追踪结果，但是你也可以用一些不太好看的条件语句绕过它...

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;

public class BetterPathfinder {

    public class Comperator implements Comparator<Path> {

        @Override
        public int compare(Path o1, Path o2) {
            return o1.getValue().compareTo(o2.getValue());
        }
    }

    public class Path {

        private Integer lenght;
        TreeMap<Integer, String> trace = new TreeMap<>();

        public Path(int lenght) {
            this.lenght = lenght;
        }

        public Path(Path find, int i, int j) {
            this.lenght = find.getValue() + 1;
            this.trace.putAll(find.getTrace());

            this.trace.put(lenght, "(" + i + "," + j + ")");
        }

        private Map<Integer, String> getTrace() {
            return trace;
        }

        public Integer getValue() {
            return lenght;
        }

        @Override
        public String toString() {
            String res = "end";
            for (Entry<Integer, String> is : trace.entrySet()) {
                res = is.getValue() + "->" + res;
            }
            return res;
        }

    }

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

    public BetterPathfinder(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 } };

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

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

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

        System.out.println(new Path(find(i, j), i, j));
    }

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

        ArrayList<Path> test = new ArrayList<>();

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

        if (i > 0 && matrix[i - 1][j] > value) {
            next[0] = i - 1;
            next[1] = j;

            test.add(new Path(find(next[0], next[1]), next[0], next[1]));
        }
        if (j > 0 && matrix[i][j - 1] > value) {
            next[0] = i;
            next[1] = j - 1;
            test.add(new Path(find(next[0], next[1]), next[0], next[1]));
        }
        if (i < matrixLenghtI - 1 && matrix[i + 1][j] > value) {
            next[0] = i + 1;
            next[1] = j;
            test.add(new Path(find(next[0], next[1]), next[0], next[1]));
        }
        if (j < matrixLenghtJ - 1 && matrix[i][j + 1] > value) {
            next[0] = i;
            next[1] = j + 1;
            test.add(new Path(find(next[0], next[1]), next[0], next[1]));
        }

        if (test.isEmpty()) {
            return new Path(100);
        }

        return Collections.min(test, new Comperator());
    }
}

结果：

(0,0)->(1,0)->(1,1)->(1,2)->(2,2)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4)->end
(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)->end
0

你需要一种递归策略。一种相当简单但代价高昂的方法是简单地淹没整个棋盘，类似于“尝试每条可能的路径并计算距离”。

你可以通过想象移动小石子来递归地实现这一点。

public int shortestPath(Point src, Point dest) {
    if (src.equals(dest)) {
            return 0;
    }

    // You need to do some bound checks here
    int left = shortestPath(new Point(src.x - 1, src.y), dest);
    int right = shortestPath(new Point(src.x + 1, src.y), dest);
    int up = shortestPath(new Point(src.x, src.y + 1), dest);
    int down = shortestPath(new Point(src.x, src.y - 1), dest);

    // Decide for the direction that has the shortest path
    return min(left, right, up, down) + 1;
}

如果您对解决方案所代表的路径感兴趣，可以在创建时跟踪该路径。为此，您只需要保存min决定的方向。

很久以前，在我的计算机科学研究中，我需要解决一个类似的任务。我们需要计算一个骑士在棋盘上到达给定目的地所需的最短移动次数。也许这也能帮助您：http://pastebin.com/0xwMcQgj

0

这是我的解决方法，请注意在你的示例中我们应该得到16

public static void main(String[] args)
{
    int[][] mat = 
        { 
                { 3, 13, 15, 28, 30 }, 
                { 40, 51, 52, 29, 30 }, 
                { 28, 10, 53, 54, 53 }, 
                { 53, 12, 55, 53, 60 },
                { 70, 62, 56, 20, 80 }, 
                { 80, 81, 90, 95, 100 } 
        };
    System.out.println(shortestPath(mat)); // 10
    
    int[][] mat1 = 
        {
            {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}
        };
    
    System.out.println(shortestPath(mat1)); // 16
}

public static int shortestPath(int[][] mat)
{
    return shortestPath(mat, 0, 0, mat[0][0] - 1, 0);
}

private static int shortestPath(int[][] mat, int row, int col, int prev, int counter)
{
    if (row < 0 || row == mat.length || col < 0 || col == mat[row].length) // boundaries
        return Integer.MAX_VALUE;

    if (mat[row][col] <= prev || mat[row][col] == -999) // if the sequence is not ascending or if we have been in this cell before
        return Integer.MAX_VALUE;

    if (row == mat.length - 1 && col == mat[row].length - 1)
        return counter + 1;

    int temp = mat[row][col];
    mat[row][col] = -999;

    int up    = shortestPath(mat, row - 1, col, temp, counter + 1); // go up and count
    int down  = shortestPath(mat, row + 1, col, temp, counter + 1);
    int left  = shortestPath(mat, row, col - 1, temp, counter + 1);
    int right = shortestPath(mat, row, col + 1, temp, counter + 1);

    mat[row][col] = temp;

    return Math.min(Math.min(up, down), Math.min(left, right)); // get the min
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接