/* * main.cpp * * Created on: Dec 15, 2017 * Author: khoa */ #include using namespace std; int N; // queue node used in BFS struct Node { int x, y; vector > path; bool const operator==(const Node& ob) const { return x == ob.x && y == ob.y; } bool operator<(const Node& ob) const { return x < ob.x || (x == ob.x && y < ob.y); } }; int row[] = {-2, -2, 0, 2, 2, 0}; int col[] = {-1, 1, 2, 1, -1, -2}; bool isValid(int x, int y) { return (x >= 0 && x < N) && (y >= 0 && y < N); } void printPath(vector > path) { /// cout << "Destination Found:\t"; // for (pair p: path) // cout << "(" << p.first << ", " << p.second << ") "; for (int i =0 ; i < path.size()-1; i++) { pair p = path[i]; int x1 = p.first; int y1 = p.second; pair q = path[i+1]; int x2 = q.first; int y2 = q.second; int k; for ( k = 0; k < 6; k++) { if(x2 == (x1 + row[k]) && y2 == (y1 +col[k])) break; } switch(k) { case 0: cout << "UL "; break; case 1: cout << "UR "; break; case 2: cout << "R "; break; case 3: cout << "LR "; break; case 4: cout << "LL "; break; case 5: cout << "L "; break; } } cout << endl; } int findPath( int x, int y , int dx, int dy) { vector > path; path.push_back({x, y}); queue Q; Node src = {x, y, path}; Q.push(src); map visited; visited[src] = true; while (!Q.empty()) { Node curr = Q.front(); Q.pop(); int i = curr.x, j = curr.y; path = curr.path; if (i == dx && j == dy) { cout << path.size() - 1 << "\n"; printPath(path); return path.size() - 1; } for (int k = 0; k < 6; k++) { int x = i + row[k]; int y = j + col[k]; if (isValid(x, y)) { path.push_back({x, y}); Node next = {x, y, path}; if (!visited.count(next)) { Q.push(next); visited[next] = true; } path.pop_back(); } } } return INT_MAX; } int main() { int n; cin >> n; N = n; int i_start; int j_start; int i_end; int j_end; cin >> i_start >> j_start >> i_end >> j_end; int cost = findPath(i_start, j_start , i_end, j_end); if(cost == INT_MAX) cout << "Impossible\n"; return 0; }