BFS Knight on chessboard (logic error somewhere)

programming
amazon
interview-questions
Tags: #<Tag:0x00007f1827df4cd8> #<Tag:0x00007f1827df4b70> #<Tag:0x00007f1827df4a08>

#1

I’m using BFS to traverse matrix and find the shortest path. I’m only accessing node if it’s possible to go there and then setting its value to visited. However, I’m not getting the right answer and I can’t understand why. Any help is appreciated!

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<>(); 
        
        Node n = new Node(sr, sc, 0);
        q.add(n);
        
//possible moves a knight can make
        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();
            for(int[] i : SHIFTS) {
                matrix[cur.row][cur.col] = -1; //set to -1 if visited
                if(cur.row == er && cur.col == ec) {
                    return cur.count;
                }
                if(canTraverse(matrix, cur.row + i[0], cur.col + i[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;
    }
}