Simple BFS Solution using level array to store minimum moves


#1

Blockquote

int X[] = {-2, -2, -1, 1, 2, 2, 1, -1};
int Y[] = {-1, 1, 2, 2, 1, -1, -2, -2};

int Solution::knight(int A, int B, int C, int D, int E, int F) {
set<pair<int,int>> visited;
queue<pair<int,int>> q;
q.push({C,D});
visited.insert({C,D});
int level[A+1][B+1];
memset(level, 0 , sizeof(level));
while(!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
if (x == E && y ==F) {
return level[E][F];
}
for(int i = 0; i< 8; i++)
{
int newx = x + X[i];
int newy = y + Y[i];
if(newx >= 1 && newx <= A && newy >= 1 && newy <= B
&& visited.find(make_pair(newx,newy)) == visited.end())
{
level[newx][newy] = level[x][y] + 1;
visited.insert({newx,newy});
q.push({newx,newy});
}
}
}
return -1;
}