矩阵中从源移动到目的地的最少马步数

Question

我的目标是使用矩阵中的最短步数从 source 移动到 destination，只进行马移动（L 形移动）

基于深度优先搜索的解决方案是否适用于这种情况？我对处理已访问节点的方式感到担忧。请让我知道这是否是一个有效的解决方案。

public class knightminmoves {

    /**
     * @param args
     */
    public static void main( String[] args ) {
        // TODO Auto-generated method stub

        int degree = 5;
        int[][] board = new int[degree][degree];
        boolean[][] visited = new boolean[degree][degree];

        System.out.println( minMoves( 0, 0, degree - 1, degree - 1, board, visited ) );
    }


    static int minMoves( int x, int y, int destx, int desty, int[][] board, boolean[][] visited ) {
        if ( x < 0 || y < 0 || x >= board.length || y >= board[0].length )
            return Integer.MAX_VALUE - 2;

        if ( x == destx && y == desty )
            return 0;

        if ( visited[x][y] == true )
            return Integer.MAX_VALUE - 2;
        else
            visited[x][y] = true;

        int upleft = minMoves( x - 2, y - 1, destx, desty, board, visited );
        int upright = minMoves( x - 2, y + 1, destx, desty, board, visited );
        int downleft = minMoves( x + 2, y - 1, destx, desty, board, visited );
        int downright = minMoves( x + 2, y + 1, destx, desty, board, visited );
        int leftup = minMoves( x - 1, y - 2, destx, desty, board, visited );
        int leftdown = minMoves( x + 1, y - 2, destx, desty, board, visited );
        int rightup = minMoves( x - 1, y + 2, destx, desty, board, visited );
        int rightdown = minMoves( x + 1, y + 2, destx, desty, board, visited );

        visited[x][y] = false;

        return min( upleft, upright, downleft, downright, leftup, leftdown, rightup, rightdown ) + 1;
    }

    static int min( int a, int b, int c, int d, int e, int f, int g, int h ) {
        int[] arr = new int[8];
        arr[0] = a;
        arr[1] = b;
        arr[2] = c;
        arr[3] = d;
        arr[4] = e;
        arr[5] = f;
        arr[6] = g;
        arr[7] = h;

        Arrays.sort( arr );
        return arr[0];
    }

}

Answer 1

你的代码是正确的，但是速度很慢。它不是深度优先搜索。由于它将访问过的节点标记为未访问过，因此您的程序只会生成所有简单路径并选择最短的路径。这是一个详尽的搜索。它具有指数级的时间复杂度，因此在更大的板上完成它需要很长时间。您可以使用广度优先搜索来获得有效且正确且可扩展的解决方案。

矩阵中从源移动到目的地的最少马步数

Minimum number of knight moves to move from source to destination in a matrix

java

algorithm

breadth-first-search

dynamic-programming

depth-first-search