#include #include using namespace std; void printShortestPath(int n, int i_end, int j_end, int i_start, int j_start) { queue> q; bool found = false; q.push(make_pair(i_end, j_end)); int dx[6] = {-2, -2, 0, 2, 2, 0}; int dy[6] = {-1, 1, 2, 1, -1, -2}; vector v = {"UL", "UR", "R", "LR", "LL", "L"}; //vector v = {"LR", "LL", "L", "UL", "UR", "R"}; vector> visited (n, vector(n, 0)); vector> level (n, vector(n, 0)); visited[i_end][j_end] = 10; level[i_end][j_end] = 0; while(!q.empty()) { pair p = q.front(); q.pop(); if (p.first == i_start && p.second == j_start) { found = true; break; } /* for (int i = 0 ; i < n; i++) { for (int j = 0; j < n; j++) { cout << visited[i][j] << " "; } cout << "\n"; } cout <<"\n"; */ //cout << p.first << " " << p.second << "\n"; for (int k = 1; k < 7; k++) { int x = p.first + dx[k-1]; int y = p.second + dy[k-1]; if (x < 0 || x >= n || y < 0 || y >= n) { continue; } if (visited[x][y] == 0) { visited[x][y] = k; level[x][y] = level[p.first][p.second] + 1; if (x == i_start && y == j_start) { found = true; break; } q.push(make_pair(x, y)); } } if (found) { break; } } if (!found) { cout << "Impossible"; } else { int i = i_start; int j = j_start; vector trace (0); cout << level[i][j] << "\n"; while (i != i_end || j != j_end) { trace.push_back(visited[i][j]-1); int i2 = i - dx[visited[i][j]-1]; int j2 = j - dy[visited[i][j]-1]; i = i2; j = j2; } for (i = trace.size() - 1; i >= 0; i--) { cout <> n; int i_start; int j_start; int i_end; int j_end; cin >> i_start >> j_start >> i_end >> j_end; printShortestPath(n, i_start, j_start, i_end, j_end); return 0; }