#include <iostream>
#include <map>
#include <queue>
#include <climits>
using namespace std;
int row[] = { 2, 2, -2, -2, 1, 1, -1, -1 };
int col[] = { -1, 1, 1, -1, 2, -2, 2, -2 };
int n;
vector<int> xcor;
vector<int> ycor;
bool valid(int x, int y)
{
return (x < 0 || y < 0 || x >= n || y >= n);
}
struct Node
{
int x, y, dist;
Node(int x, int y, int dist = 0) : x(x), y(y), dist(dist) {}
bool operator<(const Node& o) const
{
return x < o.x || (x == o.x && y < o.y);
}
};
int BFS(Node st, Node nd)
{
map<Node, bool> visited;
queue<Node> q;
q.push(st);
while (!q.empty())
{
Node node = q.front();
q.pop();
int x = node.x;
int y = node.y;
int dist = node.dist;
if (x == nd.x && y == nd.y)
return dist;
if (!visited.count(node))
{
visited[node] = false;
for (int i = 0; i < 8; ++i)
{
int x1 = x;
if (row[i] < 0 ? x > abs(row[i]) : x < INT_MAX - row[i])
x1 += row[i];
int y1 = y;
if (col[i] < 0 ? y > abs(col[i]) : y < INT_MAX - col[i])
y1 += col[i];
if (x1 != x && y1 != y) {
q.push({x1, y1, dist + 1});
}
}
}
}
return INT_MAX;
}
int main()
{
int x, y, x1, y1;
cin >> n >> x >> y >> x1 >> y1;
Node start = { x, y };
Node end = { x1, y1 };
cout<<BFS(start, end);
for(int i = 0; i < xcor.size(); ++i)
cout << xcor[i] << ' ' << ycor[i] << endl;
return 0;
}#include <iostream>
#include <set>
#include <queue>
#include <climits>
using namespace std;
int row[] = { 2, 2, -2, -2, 1, 1, -1, -1 };
int col[] = { -1, 1, 1, -1, 2, -2, 2, -2 };
bool isValid(int x, int y, int N) {
return (x >= 0 && x < N) && (y >= 0 && y < N);
}
int bfs(int N, int x,int y, int x1, int y1)
{
set<pair<int, int>> visited;
queue<pair<int, int>> q;\
pair <int, int> temp;
temp = make_pair(x, y);
q.push(temp);
while (!q.empty()) {
pair<int, int> node = q.front();
q.pop();
int dist = 0;
if (x == x1 && y == y1) {
return dist;
}
if (!visited.count(node)) {
visited.insert(node);
for (int i = 0; i < 8; i++) {
int x1 = x + row[i];
int y1 = y + col[i];
if (isValid(x1, y1, N)) {
q.push(make_pair(x1, y1));
}
}
}
}
return INT_MAX;
}
int main()
{
int N;
cin >> N;
N++;
int x, y, x1, y1;
cin >> x >> y;
cin >> x1 >> y1;
cout << bfs(N, x, y, x1, y1);
return 0;
}