Knight on Chess Board - Shortest Path

Question

I'm trying to solve this problem: https://www.interviewbit.com/problems/knight-on-chess-board/#

Basically, you're given a board, a start point and an end point and have to find the shortest path. I'm trying to do BFS on the the board using the 8 possible moves a knight can make and returning the number of moves it took, or -1 if there was no solution. I'm getting a run time out of memory error. I'm not sure where the error (or potential errors) are occurring.

Edit: Previously I was getting an error because I forgot got to mark nodes as visited. I've added that in but I'm still not getting the right answer.

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;
    }
}

Eloy Pérez Torres Eloy Pérez Torres · Accepted Answer · 2020-10-04T06:19:24

BFS algorithm needs to mark every visited position (node) to work properly. Else, such code could cause (almost certainly) runtime error or memory limit exceded (in short terms: A calls B and B calls A).

Solution: Create a boolean array and mark the nodes at the time they enter to the queue and you are done.

Knight on Chess Board - Shortest Path

1 Answers