#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; const int INF = 1000000; template std::ostream& operator<<(std::ostream& os, const vector& X) { for (const auto& x : X) os << x << ' '; return os; } using Row = vector; using Matrix = vector; struct Point { Point(int xx, int yy) : x(xx), y(yy) {} int x; int y; }; std::ostream& operator<<(std::ostream& os, const Point& X) { os << '(' << X.x << ',' << X.y << ')'; return os; } class Graph { public: Graph(int N) : n(N) {} int num_vertices() const { return n*n; } bool is_valid(const Point& P) const { return P.x >= 0 && P.x < n && P.y >= 0 && P.y < n; } void print_type(const Point& A, const Point& B) { int dx = B.x-A.x; int dy = B.y-A.y; if (dx == 2 && dy == 1) { cout << "LR"; } if (dx == 2 && dy == -1) { cout << "LL"; } if (dx == 0 && dy == 2) { cout << "R"; } if (dx == 0 && dy == -2) { cout << "L"; } if (dx == -2 && dy == 1) { cout << "UR"; } if (dx == -2 && dy == -1) { cout << "UL"; } } vector filter(const vector& P) const { vector result; result.reserve(6); for (auto& p : P) { if (is_valid(p)) result.emplace_back(get_vertex(p)); } return result; } vector neighbors(int v) const { Point P = get_coords(v); Point UL(P.x-2,P.y-1); Point UR(P.x-2,P.y+1); Point R(P.x,P.y+2); Point LR(P.x+2,P.y+1); Point LL(P.x+2,P.y-1); Point L(P.x,P.y-2); vector todos = {UL,UR,R,LR,LL,L}; return filter(todos); } vector outneighbors(int v) const { return neighbors(v); } vector inneighbors(int v) const { Point P = get_coords(v); Point UL(P.x-2,P.y-1); Point UR(P.x-2,P.y+1); Point R(P.x,P.y+2); Point LR(P.x+2,P.y+1); Point LL(P.x+2,P.y-1); Point L(P.x,P.y-2); vector todos = {LR,LL,L,UL,UR,R}; return filter(todos); } int get_vertex(int x, int y) const { return x*n+y; } int get_vertex(const Point& P) const { return get_vertex(P.x,P.y); } Point get_coords(int v) const { return Point(v/n, v%n); } int n; }; int INVALID_VERTEX = -1; struct DummyPath { DummyPath(int l, int w) : last(l), m_weight(w) {} int last; int m_weight; }; inline bool operator<(const DummyPath& a, const DummyPath& b) { return a.m_weight > b.m_weight; } class Path { public: Path(size_t n) : m_path(), m_explored(n), m_value(0) {} Path(size_t n, int initialvertex) : m_path(), m_explored(n), m_value(0) { emplace_back(initialvertex); } inline operator const std::deque&() const { return m_path; } // inline operator std::vector&() { return m_path; } long value() const { return m_value; } long cost() const { return m_value; } long weight() const { return m_value; } void push_back(const int& v) { assert(v < m_explored.size()); ++m_explored[v]; m_value += 1; m_path.push_back(v); } void emplace_back(int vertex, int w = 1) { ++m_explored[vertex]; m_value += w; m_path.emplace_back(vertex); } void push_front(int v) { // swap(m_path.front().m_weight,v.m_weight); assert(!m_path.empty() && "Use push_back when it's empty"); assert(v < m_explored.size()); m_path.emplace_front(v); m_value += 1; ++m_explored[v]; } void emplace_front(int vertex, int w = 1) { // auto w = m_path.front().m_weight; assert(!m_path.empty() && "Use emplace_back when it's empty"); assert(vertex < m_explored.size()); m_path.emplace_front(vertex); m_value += 1; ++m_explored[vertex]; } void pop_back() { assert(!m_path.empty() && "Can't pop when it's already empty!"); auto v = m_path.back(); --m_explored[v]; m_value -= 1; m_path.pop_back(); } void pop_front() { assert(!m_path.empty() && "Can't pop when it's already empty!"); auto v = m_path.front(); --m_explored[v]; m_path.pop_front(); --m_value; } void clear() { m_value = 0; // m_explored = std::vector(m_explored.size(),0); auto n = m_explored.size(); m_explored.clear(); m_explored.resize(n,0); m_path.clear(); } int operator[](size_t i) const { return m_path[i]; } int& operator[](size_t i) { return m_path[i]; } bool empty() const { return m_path.empty(); } size_t size() const { return m_path.size(); } template int first_not_explored_binary(const std::vector& Vertices, int start, Compare comp) const { auto it = std::upper_bound(Vertices.begin(), Vertices.end(), start, comp); // ++it; while (it != Vertices.end() && m_explored[*it]) ++it; if (it == Vertices.end()) return int(INVALID_VERTEX); return *it; } int first_not_explored_binary(const std::vector& Vertices, int start) const { return first_not_explored_binary(Vertices,start,std::less()); } int first_not_explored(const std::vector& Vertices, int start) const { bool seenstart = false; for (auto x : Vertices) { if (x == start) { seenstart = true; continue; } if (seenstart && !m_explored[x]) return x; } return int(INVALID_VERTEX); } int first_not_explored(const std::vector& Vertices) const { for (auto x : Vertices) { if (!m_explored[x]) return x; } return int(INVALID_VERTEX); } int back() const { return m_path.back(); } int front() const { return m_path.front(); } private: std::deque m_path; std::vector m_explored; // std::vector m_explored; long m_value; public: const decltype(m_path)& data() const { return m_path; } }; struct DummyPathWithHeuristic { DummyPathWithHeuristic(int l, int w, int h) : last(l), m_weight(w), heuristic(h) {} int last; int m_weight; int heuristic; }; inline bool operator<(const DummyPathWithHeuristic& a, const DummyPathWithHeuristic& b) { auto awph = a.m_weight + a.heuristic; auto bwph = b.m_weight + b.heuristic; if (awph > bwph) return true; if (awph < bwph) return false; return a.heuristic < b.heuristic; } template std::pair,int> AstarCostOnly(const Graph_t& G, int source, Objective obj, Heuristic h) { auto n = G.num_vertices(); // cout << "n = " << n << endl; std::vector DP(n,INF); std::priority_queue frontier; frontier.push(DummyPathWithHeuristic(source,0,h(source))); DP[source] = 0; // bool solfound = false; int costofsol = INF; int solvertex = INVALID_VERTEX; while (!frontier.empty()) { auto P = frontier.top(); // cout << "Popped " << P.last << " with m_weight " << P.m_weight << endl; frontier.pop(); if (P.m_weight > DP[P.last] || P.m_weight > costofsol) { continue; } if (obj(P.last)) { // solfound = true; costofsol = P.m_weight; solvertex = P.last; continue; } for (auto v : G.outneighbors(P.last)) { // cout << "\t v = " << v << endl; int t = 1 + P.m_weight; if (DP[v] > t) { DP[v] = t; frontier.push(DummyPathWithHeuristic(v,t,h(v))); } } } return make_pair(DP,solvertex); } template inline Path CreatePath(const Graph_t& G, int source, int destination, const std::vector& DP,bool reverse_graph = false) { assert(DP[source] == 0); Path P(G.num_vertices()); if (destination == INVALID_VERTEX || DP[destination] == INF) // nope { return P; } P.emplace_back(destination,0); // cout << "adding " << G.get_coords(destination) << endl; // int i = 0; auto totalcost = DP[destination]; // cout << "starting search from " << G.get_coords(source) << " to " << G.get_coords(destination) << endl; while (P.front() != source) { auto l = P.front(); auto Neigh = G.inneighbors(l); std::reverse(Neigh.begin(), Neigh.end()); for (auto v : Neigh) { if (totalcost == P.cost() + 1 + DP[v]) { P.push_front(v); // cout << "adding (to front): " << G.get_coords(v) << endl; break; } // cout << G.get_coords(v) << " not added because totalcost = " << totalcost << " and P.cost() = " << P.cost() << " and DP[v] = " << DP[v] << endl; } if (P.front() == l) { assert(false); } } return P; } void printasmat(const vector& A, int n) { assert(A.size() == n*n); for (int x = 0; x < n; ++x) { for (int y = 0; y < n; ++y) { if (A[x*n+y] != INF) cout << A[x*n+y] << ' '; else cout << "* "; } cout << endl; } } template Path Astar(const Graph_t& G, int source, Objective obj, Heuristic h) { auto DPandobj = AstarCostOnly(G,source,obj,h); // cout << "cost: " << endl; // printasmat(DPandobj.first,G.n); return CreatePath(G,source,DPandobj.second,DPandobj.first); } template Path Astar(const Graph_t& G, int source, int to, Heuristic h) { auto obj = [to](const int a) { return a == to; }; return Astar(G,source,obj,h); } template Path Astar(const Graph_t& G, int source, Objective obj) { auto h = [](const int a) { return 0; }; return Astar(G,source,obj,h); } template Path Astar(const Graph_t& G, int source, int to) { auto obj = [to](const int a) { return a == to; }; auto h = [](const int a) { return 0; }; return Astar(G,source,obj,h); } struct DummyPathWithHeuristicAndStart { DummyPathWithHeuristicAndStart(int l, int w, int h, bool s) : last(l), m_weight(w), heuristic(h), start(s) {} int last; int m_weight; int heuristic; bool start; }; inline bool operator<(const DummyPathWithHeuristicAndStart& a, const DummyPathWithHeuristicAndStart& b) { auto awph = a.m_weight + a.heuristic; auto bwph = b.m_weight + b.heuristic; if (awph > bwph) return true; if (awph < bwph) return false; return a.heuristic < b.heuristic; } void printShortestPath(int n, int xstart, int ystart, int xend, int yend) { Matrix A(n,Row(n,INF)); A[xend][yend] = 0; vector frontier; frontier.push_back(Point(xend,yend)); while (!frontier.empty()) { frontier.pop_back(); } } 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; Graph G(n); // cout << G.num_vertices() << endl; Point end(i_end,j_end); auto path = Astar(G,G.get_vertex(i_start, j_start), G.get_vertex(i_end,j_end),[&G,&end](int v) { Point V = G.get_coords(v); int dx = abs(V.x - end.x); int dy = abs(V.y - end.y); return (dx + dy)/3; }); if (!path.empty()) { cout << path.size()-1 << endl; for (int i = 0; i+1 < path.size(); ++i) { // cout << G.get_coords(path[i]) << "-->" << G.get_coords(path[i+1]) << endl; G.print_type(G.get_coords(path[i]),G.get_coords(path[i+1])); cout << ' '; } cout << endl; } else { cout << "Impossible" << endl; } return 0; }