#include #include #include #include #include #include #include using namespace std; typedef map>> Graph; struct Point { int i; int j; string p; Point(){ i = 0; j = 0; } Point(int i, int j) { this->i = i; this->j = j; } Point(const Point &rhs) { p = rhs.p; i = rhs.i; j = rhs.j; } const Point & operator=(const Point &rhs) { p = rhs.p; i = rhs.i; j = rhs.j; return *this; } }; void printP(const Point &p) { cout << "("<< p.i << "," << p.j << ")"; } inline Point UL(const Point &p) { return Point(p.i-2, p.j-1); } inline Point UR(const Point &p) { return Point(p.i-2, p.j+1); } inline Point R(const Point &p) { return Point(p.i, p.j+2); } inline Point LR(const Point &p) { return Point(p.i+2, p.j+1); } inline Point LL(const Point &p) { return Point(p.i+2, p.j-1); } inline Point L(const Point &p) { return Point(p.i, p.j-2); } inline bool pointIsValid(const Point &p, const int &dimension) { return (p.i >= 0 && p.i < dimension) && (p.j >= 0 && p.j < dimension); } inline int reprPoint(const Point &p, const int &dimension) { return (p.i * dimension) + p.j; } inline Point unReprPoint(const int &p, const int &dimension) { return Point(p / dimension, p % dimension); } void buildGraph(const Point &start, Graph &graph, const int &dimension) { int currentPointRepr; Point tmp, currentPoint; vector horizon; horizon.push_back(start); vector> transformations { {"UL", UL}, {"UR", UR}, {"R", R}, {"LR", LR}, {"LL", LL}, {"L", L} }; while (! horizon.empty()) { currentPoint = horizon.back(); horizon.pop_back(); currentPointRepr = reprPoint(currentPoint, dimension); for (auto & f : transformations) { tmp = f.second(currentPoint); if (pointIsValid(tmp, dimension)) { auto repr = make_pair(reprPoint(tmp, dimension), f.first); if (graph[currentPointRepr].find(repr) == graph[currentPointRepr].end()) { horizon.push_back(tmp); graph[currentPointRepr].insert(repr); } } } } } void printShortestPath(Graph &graph, const Point &src, const Point &target, const int &dimension) { map> path; map distance; map visited; priority_queue, greater> q; for (auto & node : graph) { distance[node.first] = std::numeric_limits::max(); visited[node.first] = false; } distance[reprPoint(src, dimension)] = 0; path[reprPoint(src, dimension)] = {-1, ""}; q.push(reprPoint(src, dimension)); while (! q.empty()) { int current = q.top(); q.pop(); visited[current] = true; if (distance[current] == std::numeric_limits::max()) break; for (auto &adjacent : graph[current]) { if (! visited[adjacent.first]) { q.push(adjacent.first); } auto str = graph[current].find(adjacent)->second; if (distance[adjacent.first] > (distance[current] + 1) || (distance[adjacent.first] == (distance[current] + 1) && path[current].second > str) ) { distance[adjacent.first] = distance[current] + 1; path[adjacent.first] = {current, str}; } } } int current = reprPoint(target, dimension); if (path[current].first == 0) { cout << "Impossible" << endl; return; } else { vector finalPath; while (path[current].first != -1) { finalPath.push_back(path[current].second); current = path[current].first; } cout << distance[reprPoint(target, dimension)] << endl; for (int i = finalPath.size() - 1; i >= 0; --i) { cout << finalPath[i] << " "; } } cout << endl; } void printGraph(Graph &graph, const int &dimension) { for (auto iter = graph.begin(), end = graph.end(); iter != end; ++iter) { cout << iter->first << " "; for (auto iter2 = iter->second.begin(), end2 = iter->second.end(); iter2 != end2; ++iter2) { printP(unReprPoint(iter2->first, dimension)); cout << " "; } cout << endl; } } int main() { Point start, target; int dimension; Graph graph; cin >> dimension; cin >> start.i; cin >> start.j; cin >> target.i; cin >> target.j; buildGraph(start, graph, dimension); //printGraph(graph, dimension); printShortestPath(graph, start, target, dimension); return 0; }