https://practice.geeksforgeeks.org/problems/steps-by-knight/0

class pos {
public:
  int x, y, dist;

  pos(int x, int y, int dist) : x(x), y(y), dist(dist) {}
};

class Solution {
  bool isInside(int x, int y, int N) {
    return (x >= 1 and x <= N and y >= 1 and y <= N);
  }

public:
  int minStepToReachTarget(vector<int> &KnightPos, vector<int> &TargetPos,
                           int N) {
    vector<pair<int, int>> dir = {
        {-2, -1}, {-1, -2}, {1, -2}, {2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1},
    };

    bool visited[N + 1][N + 1] = {0};
    queue<pos> q;

    q.push(pos(KnightPos[0], KnightPos[1], 0));
    visited[KnightPos[0]][KnightPos[1]] = true;

    while (!q.empty()) {
      pos currPos = q.front();
      q.pop();

      if (currPos.x == TargetPos[0] and currPos.y == TargetPos[1]) {
        return currPos.dist;
      }
      for (int i = 0; i < 8; i++) {
        int x = currPos.x + dir[i].first;
        int y = currPos.y + dir[i].second;

        if (isInside(x, y, N) and !visited[x][y]) {
          q.push(pos(x, y, currPos.dist + 1));
          visited[x][y] = true;
        }
      }
    }
  }
};