/* * Source.cpp * * Created on: Dec 4, 2017 * Author: nxuantruong */ #include #include #include #include #include #include #include using namespace std; struct cordinate { int x, y; }; int RMOVE[] = { -2, -2, 0, 2, 2, 0 }; int CMOVE[] = { -1, 1, 2, 1, -1, -2 }; string name[] = { "UL", "UR", "R", "LR", "LL", "L" }; int n; int a[200][200], b[200][200]; int cs, rs, ce, re; cordinate knight; bool isValid(int x, int y) { if (x < 0 || x >= n || y < 0 || y >= n) return false; return true; } void printResult() { cordinate start; string rs = ""; int length = 0; start.x = re; start.y = ce; while (start.x != knight.x || start.y != knight.y) { int pos = b[start.x][start.y]; length++; rs = name[pos] + " " + rs; start.x -= RMOVE[pos]; start.y -= CMOVE[pos]; } cout << length << endl << rs; } int main() { queue q; bool ok = false; cin >> n >> knight.x >> knight.y >> re >> ce; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) b[i][j] = -1; b[knight.x][knight.y] = 7; memset(a, 0, sizeof(a)); q.push(knight); while (!q.empty()) { cordinate temp, k = q.front(); q.pop(); if (ok) break; for (int i = 0; i < 6; ++i) { temp.x = k.x + RMOVE[i]; temp.y = k.y + CMOVE[i]; if (isValid(temp.x, temp.y) && !a[temp.x][temp.y]) { if (temp.x == re && temp.y == ce) { b[temp.x][temp.y] = i; printResult(); ok = true; // Done } else if (b[temp.x][temp.y] < 0){ b[temp.x][temp.y] = i; q.push(temp); } } } } if (!ok) cout << "Impossible"; }