Минимальное количество рыцаря движется, чтобы перейти от источника к месту назначения в матрице

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

Ваш код верный, но он медленный. Это не поиск по глубине. Поскольку он отмечает посещаемый узел как невидимый, ваша программа просто генерирует все простые пути и выбирает самый короткий. Это исчерпывающий поиск. Он имеет экспоненциальную временную сложность, поэтому для больших плат потребуется слишком много времени. Вы можете использовать поиск по ширине, чтобы получить эффективное и правильное решение, которое хорошо масштабируется.