/+ dub.sdl: name "A" dependency "dcomp" version=">=0.9.0" +/ import std.stdio, std.algorithm, std.range, std.conv; // import dcomp.foundation, dcomp.scanner; // import dcomp.array, dcomp.dungeon, dcomp.container.deque; immutable int[2][6] d6 = [ [-2, -1], [-2, 1], [0, 2], [2, 1], [2, -1], [0, -2], ]; int main() { Scanner sc = new Scanner(stdin); int n; sc.read(n); int[2] sv, tv; sc.read(sv[0], sv[1], tv[0], tv[1]); int[][] di = iota(n).map!(_ => (10^^9).repeat.take(n).array).array; bool[][] vis = new bool[][](n, n); int[][] ty = new int[][](n, n); int[2][][] ba = new int[2][][](n, n); di.at2D(sv) = 0; auto dh = Dungeon(n, n); Deque!(int[2]) q; q.insertBack(sv); while (q.length) { auto p = q.front; q.removeFront; if (vis.at2D(p)) continue; vis.at2D(p) = true; foreach (int i, d; d6) { auto np = addInt2(p, d); if (!dh.isInside(np)) continue; if (di.at2D(p) + 1 < di.at2D(np)) { di.at2D(np) = di.at2D(p) + 1; ba.at2D(np) = p; ty.at2D(np) = i; q.insertBack(np); } } } // writeln(di.at2D(tv)); if (di.at2D(tv) > 10^^8) { writeln("Impossible"); return 0; } int[] res; while (tv != sv) { res ~= ty.at2D(tv); tv = ba.at2D(tv); } reverse(res); string[] mt = [ "UL", "UR", "R", "LR", "LL", "L", ]; writeln(res.length); writeln(mt.indexed(res).join(" ")); return 0; } /* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/dungeon.d */ // module dcomp.dungeon; immutable static int[2][4] direction4 = [ [1, 0], [0, 1], [-1, 0], [0, -1], ]; immutable static int[2][8] direction8 = [ [1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1], ]; static int[2] addInt2(in int[2] a, in int[2] b) { int[2] c; c[] = a[] + b[]; return c; } struct Dungeon { static int[2] move4(int[2] p, int dir) { return addInt2(p, direction4[dir]); } static int[2] move8(int[2] p, int dir) { return addInt2(p, direction8[dir]); } immutable int R, C; this(int R, int C) { this.R = R; this.C = C; } bool isInside(int[2] p) const { int r = p[0], c = p[1]; return 0 <= r && r < R && 0 <= c && c < C; } int getID(int[2] p) const { int r = p[0], c = p[1]; return r*R+c; } } auto neighbors4(int[2] p) { static struct Rng { int[2] center; size_t i; bool empty() const { return i == 4;} int[2] front() const { return addInt2(center, direction4[i]); } void popFront() { i++; } } return Rng(p, 0); } auto neighbors4(int[2] p, in Dungeon dg) { static struct Rng { int[2] center; Dungeon dg; size_t i; this(in int[2] center, in Dungeon dg) { this.center = center; this.dg = dg; while (!empty() && !dg.isInside(front)) i++; } bool empty() const { return i == 4;} int[2] front() const { return addInt2(center, direction4[i]); } void popFront() { i++; while (!empty() && !dg.isInside(front)) i++; } } return Rng(p, dg); } /* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/container/deque.d */ // module dcomp.container.deque; struct DequePayload(T) { import core.exception : RangeError; private T* _data; private uint start, len, cap; @property bool empty() const { return len == 0; } @property size_t length() const { return len; } alias opDollar = length; ref inout(T) opIndex(size_t i) inout { version(assert) if (len <= i) throw new RangeError(); if (start + i < cap) return _data[start + i]; else return _data[start + i - cap]; } ref inout(T) front() inout { return this[0]; } ref inout(T) back() inout { return this[$-1]; } void reserve(size_t newCap) { import core.memory : GC; import std.algorithm : max; import std.conv : to; if (newCap <= cap) return; T* newData = cast(T*)GC.malloc(newCap * T.sizeof); foreach (i; 0..length) { newData[i] = this[i]; } _data = newData; start = 0; cap = newCap.to!uint; } void clear() { start = len = 0; } import std.algorithm : max; void insertFront(T item) { if (len == cap) reserve(max(cap * 2, 4)); if (start == 0) start += cap; start--; len++; this[0] = item; } void insertBack(T item) { if (len == cap) reserve(max(cap * 2, 4)); len++; this[len-1] = item; } void removeFront() { assert(!empty, "Deque.removeFront: Deque is empty"); start++; len--; if (start == cap) start = 0; } void removeBack() { assert(!empty, "Deque.removeBack: Deque is empty"); len--; } } struct Deque(T, bool mayNull = true) { import core.exception : RangeError; import std.range : ElementType, isInputRange; import std.traits : isImplicitlyConvertible; alias Payload = DequePayload!T; Payload* _p; static if (!mayNull) @disable this(); this(U)(U[] values...) if (isImplicitlyConvertible!(U, T)) { _p = new Payload(); foreach (v; values) { insertBack(v); } } this(Range)(Range r) if (isInputRange!Range && isImplicitlyConvertible!(ElementType!Range, T) && !is(Range == T[])) { _p = new Payload(); foreach (v; r) { insertBack(v); } } private this(Payload* p) { _p = p; } static Deque make() { return Deque(new Payload()); } private bool havePayload() const { return (!mayNull || _p); } @property bool empty() const { return (!havePayload || _p.empty); } @property size_t length() const { return (havePayload ? _p.length : 0); } alias opDollar = length; ref inout(T) opIndex(size_t i) inout { assert(!empty, "Deque.opIndex: Deque is empty"); return (*_p)[i]; } ref inout(T) front() inout { return this[0]; } ref inout(T) back() inout { return this[$-1]; } void clear() { if (_p) _p.clear(); } void insertFront(T item) { if (mayNull && !_p) _p = new Payload(); _p.insertFront(item); } void insertBack(T item) { if (mayNull && !_p) _p = new Payload(); _p.insertBack(item); } alias opOpAssign(string op : "~") = insertBack; alias stableInsertBack = insertBack; void removeFront() { assert(!mayNull || _p, "Deque.removeFront: Deque is empty"); _p.removeFront(); } void removeBack() { assert(!mayNull || _p, "Deque.removeBack: Deque is empty"); _p.removeBack(); } alias stableRemoveBack = removeBack; alias Range = RangeT!(DequePayload!T); alias ConstRange = RangeT!(const DequePayload!T); alias ImmutableRange = RangeT!(immutable DequePayload!T); size_t[2] opSlice(size_t dim : 0)(size_t start, size_t end) const { assert(start <= end && end <= length); return [start, end]; } Range opIndex(size_t[2] rng) { return Range(_p, rng[0], rng[1]); } ConstRange opIndex(size_t[2] rng) const { return ConstRange(_p, rng[0], rng[1]); } ImmutableRange opIndex(size_t[2] rng) immutable { return ImmutableRange(_p, rng[0], rng[1]); } auto opIndex() inout { return this[0..$]; } static struct RangeT(QualifiedPayload) { alias A = QualifiedPayload; import std.traits : CopyTypeQualifiers; alias E = CopyTypeQualifiers!(A, T); A *p; size_t l, r; @property bool empty() const { return r <= l; } @property size_t length() const { return r - l; } alias opDollar = length; @property auto save() { return this; } ref inout(E) opIndex(size_t i) inout { version(assert) if (empty) throw new RangeError(); return (*p)[l+i]; } @property ref inout(E) front() inout { return this[0]; } @property ref inout(E) back() inout { return this[$-1]; } void popFront() { version(assert) if (empty) throw new RangeError(); l++; } void popBack() { version(assert) if (empty) throw new RangeError(); r--; } size_t[2] opSlice(size_t dim : 0)(size_t start, size_t end) const { assert(start <= end && end <= length); return [start, end]; } auto opIndex(size_t[2] rng) { return RangeT(p, l+rng[0], l+rng[1]); } auto opIndex(size_t[2] rng) const { return RangeT!(const A)(p, l+rng[0], l+rng[1]); } auto opIndex(size_t[2] rng) immutable { return RangeT!(immutable A)(p, l+rng[0], l+rng[1]); } auto opIndex() inout { return this[0..$]; } } } /* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/array.d */ // module dcomp.array; T[N] fixed(T, size_t N)(T[N] a) {return a;} int[2] findFirst2D(T, U)(in T mp, in U c) { import std.conv : to; int R = mp.length.to!int; int C = mp[0].length.to!int; foreach (i; 0..R) { foreach (j; 0..C) { if (mp[i][j] == c) return [i, j]; } } assert(false); } auto ref at2D(T, U)(ref T mp, in U idx) { return mp[idx[0]][idx[1]]; } /* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/scanner.d */ // module dcomp.scanner; // import dcomp.container.stackpayload; class Scanner { import std.stdio : File; import std.conv : to; import std.range : front, popFront, array, ElementType; import std.array : split; import std.traits : isSomeChar, isStaticArray, isArray; import std.algorithm : map; File f; this(File f) { this.f = f; } char[512] lineBuf; char[] line; private bool succW() { import std.range.primitives : empty, front, popFront; import std.ascii : isWhite; while (!line.empty && line.front.isWhite) { line.popFront; } return !line.empty; } private bool succ() { import std.range.primitives : empty, front, popFront; import std.ascii : isWhite; while (true) { while (!line.empty && line.front.isWhite) { line.popFront; } if (!line.empty) break; line = lineBuf[]; f.readln(line); if (!line.length) return false; } return true; } private bool readSingle(T)(ref T x) { import std.algorithm : findSplitBefore; import std.string : strip; import std.conv : parse; if (!succ()) return false; static if (isArray!T) { alias E = ElementType!T; static if (isSomeChar!E) { auto r = line.findSplitBefore(" "); x = r[0].strip.dup; line = r[1]; } else static if (isStaticArray!T) { foreach (i; 0..T.length) { bool f = succW(); assert(f); x[i] = line.parse!E; } } else { StackPayload!E buf; while (succW()) { buf ~= line.parse!E; } x = buf.data; } } else { x = line.parse!T; } return true; } int read(T, Args...)(ref T x, auto ref Args args) { if (!readSingle(x)) return 0; static if (args.length == 0) { return 1; } else { return 1 + read(args); } } } /* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/foundation.d */ // module dcomp.foundation; static if (__VERSION__ <= 2070) { /* Copied by https://github.com/dlang/phobos/blob/master/std/algorithm/iteration.d Copyright: Andrei Alexandrescu 2008-. License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0). */ template fold(fun...) if (fun.length >= 1) { auto fold(R, S...)(R r, S seed) { import std.algorithm : reduce; static if (S.length < 2) { return reduce!fun(seed, r); } else { import std.typecons : tuple; return reduce!fun(tuple(seed), r); } } } } /* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/container/stackpayload.d */ // module dcomp.container.stackpayload; struct StackPayload(T, size_t MINCAP = 4) if (MINCAP >= 1) { import core.exception : RangeError; private T* _data; private uint len, cap; @property bool empty() const { return len == 0; } @property size_t length() const { return len; } alias opDollar = length; inout(T)[] data() inout { return (_data) ? _data[0..len] : null; } ref inout(T) opIndex(size_t i) inout { version(assert) if (len <= i) throw new RangeError(); return _data[i]; } ref inout(T) front() inout { return this[0]; } ref inout(T) back() inout { return this[$-1]; } void reserve(size_t newCap) { import core.memory : GC; import core.stdc.string : memcpy; import std.conv : to; if (newCap <= cap) return; void* newData = GC.malloc(newCap * T.sizeof); cap = newCap.to!uint; if (len) memcpy(newData, _data, len * T.sizeof); _data = cast(T*)(newData); } void free() { import core.memory : GC; GC.free(_data); } void clear() { len = 0; } void insertBack(T item) { import std.algorithm : max; if (len == cap) reserve(max(cap * 2, MINCAP)); _data[len++] = item; } alias opOpAssign(string op : "~") = insertBack; void removeBack() { assert(!empty, "StackPayload.removeBack: Stack is empty"); len--; } } /* This source code generated by dcomp and include dcomp's source code. dcomp's Copyright: Copyright (c) 2016- Kohei Morita. (https://github.com/yosupo06/dcomp) dcomp's License: MIT License(https://github.com/yosupo06/dcomp/blob/master/LICENSE.txt) */