HA30_Horse(3)

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Chessboard {
private:
    int N;
    vector<vector<bool> > used;
    vector<vector<pair<int, int> > > prev;
    int dx[8];
    int dy[8];

public:
    Chessboard(int size) {
        N = size;
        used.resize(N, vector<bool>(N, false));
        prev.resize(N, vector<pair<int, int> >(N, make_pair(-1, -1)));

        // Инициализация смещений для хода коня
        int temp_dx[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };
        int temp_dy[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
        for (int i = 0; i < 8; ++i) {
            dx[i] = temp_dx[i];
            dy[i] = temp_dy[i];
        }
    }

    bool is_valid(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < N;
    }

    int BFS(int x1, int y1, int x2, int y2) {
        queue<pair<int, int> > q;
        q.push(make_pair(x1, y1));
        used[x1][y1] = true;

        while (!q.empty()) {
            pair<int, int> cur = q.front();
            q.pop();
            int x = cur.first;
            int y = cur.second;

            if (x == x2 && y == y2) {
                return 0; // Мы достигли цели
            }

            for (int i = 0; i < 8; ++i) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (is_valid(nx, ny) && !used[nx][ny]) {
                    used[nx][ny] = true;
                    prev[nx][ny] = make_pair(x, y);
                    q.push(make_pair(nx, ny));
                }
            }
        }
        return -1;
    }

    vector<pair<int, int> > get_path(int x1, int y1, int x2, int y2) {
        vector<pair<int, int> > path;
        int x = x2;
        int y = y2;

        while (!(x == x1 && y == y1)) {
            path.push_back(make_pair(x, y));
            pair<int, int> p = prev[x][y];
            x = p.first;
            y = p.second;
        }
        path.push_back(make_pair(x1, y1));

        // Разворачиваем путь
        vector<pair<int, int> > reversed_path;
        for (int i = path.size() - 1; i >= 0; --i) {
            reversed_path.push_back(path[i]);
        }
        return reversed_path;
    }

    int get_move_count(int x1, int y1, int x2, int y2) {
        int moves = 0;
        int x = x2;
        int y = y2;

        while (!(x == x1 && y == y1)) {
            pair<int, int> p = prev[x][y];
            x = p.first;
            y = p.second;
            moves++;
        }
        return moves;
    }
};

int main() {
    int N, x1, y1, x2, y2;
    cin >> N >> x1 >> y1 >> x2 >> y2;

    x1--; y1--;
    x2--; y2--;

    Chessboard chessboard(N);
    chessboard.BFS(x1, y1, x2, y2);

    vector<pair<int, int> > path = chessboard.get_path(x1, y1, x2, y2);
    int move_count = path.size() - 1;

    cout << move_count << endl;
    for (size_t i = 0; i < path.size(); ++i) {
        cout << path[i].first + 1 << " " << path[i].second + 1 << endl;
    }

    return 0;
}