#include #include #include #include using namespace std; int main() { int n; cin >> n; int x1, y1; int x2, y2; cin >> x1 >> y1 >> x2 >> y2; x1--; y1--; x2--; y2--; vector> board(n, vector(n)); vector> length(n, vector(n)); vector>> parents(n, vector>(n)); queue> q; board[x2][y2] = 1; q.push(make_pair(x2, y2)); parents[x2][y2] = make_pair(x2, y2); while (!q.empty()) { pair p = q.front(); int x, y; tie(x, y) = p; q.pop(); for (int i = -2; i <= 2; i++) { for (int j = -2; j <= 2; j++) { if (abs(i) + abs(j) != 3) { continue; } int xt = x + i; int yt = y + j; if (xt < 0 || xt >= n) { continue; } if (yt < 0 || yt >= n) { continue; } if (board[xt][yt] == 0) { board[xt][yt] = 1; q.push(make_pair(xt, yt)); parents[xt][yt] = p; length[xt][yt] = length[x][y] + 1; } } } } cout << length[x1][y1] << '\n'; pair t = make_pair(x1, y1); while (t != make_pair(x2, y2)) { int x, y; tie(x, y) = t; cout << x + 1 << ' ' << y + 1 << '\n'; t = parents[x][y]; } cout << x2 + 1 << ' ' << y2 + 1; return 0; }