java - 达到国际象棋目标的最小步数-使用BFS进行骑士穿越

下面给出的代码适用于小于13号的国际象棋，但在那之后它需要太多的时间，并且永远运行。
我想缩短到达终点节点的时间。
此外，此代码还查找从starti、startj到endi、endj的最小路径，其中starti和startj的值从1到n-1。
下面是我要解决的问题：
https://www.hackerrank.com/challenges/knightl-on-chessboard/problem
程序：

import java.util.LinkedList;<br>
import java.util.Scanner;

class Node {

    int x,y,dist;

    Node(int x, int y, int dist) {
        this.x = x;
        this.y = y;
        this.dist = dist;
    }

    public String toString() {
        return "x: "+ x +" y: "+y +" dist: "+dist;
    }
}

class Solution {

    public static boolean checkBound(int x, int y, int n) {

        if(x >0 && y>0 && x<=n && y<=n)
            return true;
        return false;
    }

    public static void printAnswer(int answer[][], int n) {
        for(int i=0; i<n-1; i++) {
            for(int j=0; j<n-1; j++) {
                System.out.print(answer[i][j]+" ");
            }
            System.out.println();
        }

    }

    public static int findMinimumStep(int n, int[] start, int[] end, int a, int b) {

        LinkedList<Node> queue = new LinkedList();
        boolean visited[][] = new boolean[n+1][n+1];
        queue.add(new Node(start[0],start[1],0));
        int x,y;

        int[] dx = new int[] {a, -a, a, -a, b, -b, b, -b};
        int[] dy = new int[] {b, b, -b, -b, a, a, -a, -a};


        while(!queue.isEmpty()) {
            Node z = queue.removeFirst();
            visited[z.x][z.y] = true;

            if(z.x == end[0] && z.y == end[1])
                return z.dist;

            for(int i=0; i<8; i++)
            {
                x = z.x + dx[i];
                y = z.y + dy[i];
                if(checkBound(x,y,n) && !visited[x][y])
                    queue.add(new Node(x,y,z.dist+1));
            }
        }
        return -1;
    }

    public static void main(String args[]) {

        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int start[] = new int[] {1,1};
        int goal[] = new int[] {n,n};
        int answer[][] = new int[n-1][n-1];

        for(int i=1; i<n; i++) {
            for(int j=i; j<n; j++) {
                int result = findMinimumStep(n, start, goal, i, j);
                answer[i-1][j-1] = result;
                answer[j-1][i-1] = result;
            }
        }
        printAnswer(answer,n);

    }
}

最佳答案

设置visited太晚了，同一个单元格被多次添加到队列中，然后从队列中弹出它们，而不检查它们的访问状态，这会使情况更糟。这导致队列的快速增长。
您需要在将visited添加到队列后立即设置Node：

if(checkBound(x,y,n) && !visited[x][y]) {
    queue.add(new Node(x,y,z.dist+1));
    visited[x][y] = true;
}