#include #include #include using namespace std; int set[200][200] = { {0} }; int c; vector out; vector> queue; void BFS(int n, int i_start, int j_start, int i_end, int j_end) { queue.push_back(make_pair(i_end, j_end)); while (!queue.empty()) { pair p = queue[0]; if (p.first - 2 >= 0 && p.second - 1 >= 0) { if (set[p.first - 1][p.second - 2] == 0) { queue.push_back(make_pair(p.first - 2, p.second - 1)); set[p.first - 2][p.second - 1] = 1; } if (p.first - 2 == i_start&&p.second - 1 == j_start) return; } if (p.first - 2 >= 0 && p.second + 1= 0) { if (set[p.first + 2][p.second - 1] == 0) { queue.push_back(make_pair(p.first + 2, p.second - 1)); set[p.first + 2][p.second - 1] = 1; } if (p.first + 2 == i_start&&p.second - 1 == j_start) return; } if (p.second - 2 >= 0) { if (set[p.first][p.second-2] == 0) { queue.push_back(make_pair(p.first, p.second-2)); set[p.first][p.second-2] = 1; } if (p.first == i_start&&p.second-2 == j_start) return; } queue.erase(queue.begin()); } } void printS(int n, int i_start, int j_start, int i_end, int j_end) { // Print the distance along with the sequence of moves. for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { set[i][j] = 0; } } queue.clear(); BFS(n, i_start, j_start, i_end, j_end); if (queue.empty()) cout << "Impossible" << endl; else { c += 1; if (i_start-i_end == -2 && j_start-j_end == -1) { out.push_back( "UL "); return; } if (i_start - i_end == 0 && j_start - j_end == -2) { out.push_back( "L "); return; } if (i_start - i_end == -2 && j_start - j_end == 1) { out .push_back( "UR "); return; } if (i_start - i_end == 2 && j_start - j_end == -1) { out.push_back( "LL "); return; } if (i_start - i_end == 0 && j_start - j_end == 2) { out.push_back( "R "); return; } if (i_start - i_end == 2 && j_start - j_end == 1) { out.push_back( "LR "); return; } int x = i_start-queue[0].first; int y = j_start-queue[0].second; if (x == -2 && y == -1) out.push_back("UL "); if (x == 0 && y == -2) out.push_back( "L "); if (x == -2 && y == 1) out.push_back( "UR "); if (x == 2 && y == -1) out.push_back( "LL "); if (x == 0 && y == 2) out.push_back( "R "); if (x == 2 && y == 1) out.push_back( "LR "); printS(n, -x + i_start, -y + j_start, i_end, j_end); } } void printShortestPath(int n, int i_end, int j_end, int i_start, int j_start) { printS(n, i_start, j_start, i_end, j_end); if (c) { cout << c << endl; for (int i = 0; i < c; i++) { cout << out[c-1-i]; } } } int main() { int n; cin >> 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); system("pause"); }