# BFS Knight on chessboard (logic error somewhere)

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

Node n = new Node(sr, sc, 0);

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