bool valid(int x, int y, int n, int m)
{
if (x > 0 && y > 0 && x <= n && y <= m)
{
return true;
}
return false;
}
int Solution::knight(int A, int B, int C, int D, int E, int F)
{
bool visited[A + 1][B + 1];
int moves[A + 1][B + 1];
memset(moves, -1, sizeof(moves));
memset(visited, false, sizeof(visited));
queue<pair<int, int>> Q;
Q.push(make_pair(C, D));
visited[C][D] = true;
moves[C][D] = 0;
while (!Q.empty())
{
pair<int, int> curr = Q.front();
Q.pop();
vector<pair<int, int>> graph;
int x = curr.first, y = curr.second;
if (valid(x - 1, y - 2, A, B)) graph.push_back(make_pair(x - 1, y - 2));
if (valid(x - 1, y + 2, A, B)) graph.push_back(make_pair(x - 1, y + 2));
if (valid(x + 1, y - 2, A, B)) graph.push_back(make_pair(x + 1, y - 2));
if (valid(x + 1, y + 2, A, B)) graph.push_back(make_pair(x + 1, y + 2));
if (valid(x + 2, y - 1, A, B)) graph.push_back(make_pair(x + 2, y - 1));
if (valid(x + 2, y + 1, A, B)) graph.push_back(make_pair(x + 2, y + 1));
if (valid(x - 2, y - 1, A, B)) graph.push_back(make_pair(x - 2, y - 1));
if (valid(x - 2, y + 1, A, B)) graph.push_back(make_pair(x - 2, y + 1));
for (auto a: graph)
{
int x1 = a.first, y1 = a.second;
moves[x1][y1] = (moves[x1][y1] == -1) ? moves[x][y] + 1 : min(moves[x1][y1], moves[x][y] + 1);
if (visited[x1][y1])
{
continue;
}
Q.push(make_pair(x1, y1));
visited[x1][y1] = true;
}
}
if (visited[E][F])
{
return moves[E][F];
}
return -1;
}
