bool isValid(int x, int y, int row, int col){
if(x < 0 || y < 0 || x >= row || y >= col)return false;
return true;
}
// If reachable position is not already visited and is inside the board, we push this state into queue with distance 1 more than its parent state.
int Solution::knight(int row, int col, int x, int y, int t1, int t2) {
// all the 8 direction
int dx[8] = {-1, 1, 2, 2, 1, -1, -2, -2};
int dy[8] = {2, 2, 1, -1, -2, -2, -1, 1};
x--,y--,t1--,t2--;
vector<vector<bool>>visited(row, vector<bool>(col, false));
queue<vector<int>>q;
q.push({x, y, 0}); // {ith coord, jth coord, depth}
visited[x][y] = true;
while(!q.empty()){
vector<int>p = q.front(); q.pop();
x = p[0];
y = p[1];
int count = p[2];
if(x == t1 && y == t2)return count;
// push all possible next position of knight(at max 8)
for(int i = 0; i < 8; ++i){
x = x + dx[i];
y = y + dy[i];
if(isValid(x, y, row, col) && !visited[x][y]){
// cout<<x<<" "<<y<<endl;
visited[x][y] = true;
q.push({x, y, count+1});
}
}
}
return -1;
}
Gives wrong output!
heuit
#1