algorithm - 棋盘上的骑士-最短路径

Question

我正在尝试解决这个问题：https ://www.interviewbit.com/problems/knight-on-chess-board/#

基本上，你会得到一块棋盘、一个起点和一个终点，并且必须找到最短的路径。我正在尝试使用骑士可以进行的 8 种可能的移动并返回它所采取的移动次数在棋盘上进行 BFS，如果没有解决方案，则返回 -1。我遇到了运行时内存不足错误。我不确定错误（或潜在错误）发生在哪里。

编辑：以前我收到一个错误，因为我忘记将节点标记为已访问。我已经添加了，但我仍然没有得到正确的答案。

public class Solution {
    
    private class Node {
        int row;
        int col;
        int count;
        public Node() {
            this.row = 0;
            this.col = 0;
            this.count = 0;
        }
        public Node(int row, int col, int count) {
            this.row = row;
            this.col = col;
            this.count = count;
        }
    }
    
    public int knight(int A, int B, int sr, int sc, int er, int ec) {
        int[][] matrix = new int[A][B];
        Queue<Node> q = new LinkedList<>(); //linkedlist??
        
        Node n = new Node(sr, sc, 0);
        q.add(n);
        matrix[sr][sc] = -1; 
        final int[][] SHIFTS = {
            {-2,1},
            {-2,-1},
            {2,1},
            {2,-1},
            {-1,2},
            {-1,-2},
            {1,2},
            {1,-2}
        };
        int count = 0;
        while(!q.isEmpty()) {
            Node cur = q.remove();
            if(cur.row == er && cur.col == ec) {
                return cur.count;
            }
            for(int[] i : SHIFTS) {  
                if(canTraverse(matrix, cur.row + i[0], cur.col + i[1])) {
                    matrix[cur.row + i[0]][cur.col + i[1]] = -1;
                    q.add(new Node(cur.row + i[0], cur.col + i[1], cur.count + 1));
                }
            }
        
        }
        return -1;
    }
    
    public static boolean canTraverse(int[][] matrix, int sr, int sc) {
        if(sr < 0 || sr >= matrix.length || sc < 0 || sc >= matrix[sr].length || matrix[sr][sc] == -1) {
            return false;
        }
        return true;
    }
}

标签： algorithmgraphdepth-first-searchbreadth-first-searchshortest-path

Answer 1

BFS算法需要标记每个访问的位置（节点）才能正常工作。否则，此类代码可能会导致（几乎可以肯定）运行时错误或超出内存限制（简而言之：A 调用 B，B 调用 A）。

解决方案：创建一个布尔数组并在节点进入队列时标记节点，您就完成了。