#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>>> graph(n, vector>>(n)); vector>> parents(n, vector>(n)); for (int x = 0; x < n; x++) { for (int y = 0; y < n; y++) { 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; } graph[x][y].push_back(make_pair(xt, yt)); } } } } 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 (pair t : graph[x][y]) { int xt, yt; tie(xt, yt) = t; 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; }