import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { static int dx = 0; static int dy = 0; static int bsize = 0; static int shortest = 0; static wtmp[][] rmap = null; static boolean[][] map = null; static HashMap dmap = null; static List winners = null; private static void init() { winners = new Vector(); dmap = new HashMap(); dmap.put(Dirs.UL, Dirs.LR); dmap.put(Dirs.UR, Dirs.LL); dmap.put(Dirs.L, Dirs.R); dmap.put(Dirs.R, Dirs.L); dmap.put(Dirs.LL, Dirs.UR); dmap.put(Dirs.LR, Dirs.UL); rmap = new wtmp[bsize][bsize]; map = new boolean[bsize][bsize]; int i = 0; int j = 0; for (i=0;i (" + dx + "," + dy + ")"); init(); map[x][y] = true; innerObj start = new innerObj(x,y); loop(start); death(); for (Winner w : winners) w.Print(); if (winners.size() == 0) System.out.println("Impossible"); } private static void death() { List r = new Vector(); for (Winner w : winners) if (w.getLength() != shortest) r.add(w); winners.removeAll(r); } private static void loop(innerObj obj) { determinePossible(obj); List dl = obj.getPossible(); for (Dirs d : dl) explore(obj,d); } private static void checkShorter(innerObj obj,wtmp wobj) { Winner w = new Winner(obj); if (w.getLength() < wobj.getLength()) { Pos p = obj.getPos(); if (!((p.getX() == dx) && (p.getY() == dy))) w.merge(w,wobj); if (w.getLength() < shortest) winners.add(w); } } private static void explore(innerObj obj,Dirs d) { innerObj n = new innerObj(obj,d); Pos p = n.getPos(); if ((p.getX() == dx) && (p.getY() == dy)) { Winner w = new Winner(n); if ((shortest == 0) || (w.getLength() < shortest)) { shortest = w.getLength(); winners.add(w); } } if (map[p.getX()][p.getY()]) { wtmp w = rmap[p.getX()][p.getY()]; if (w != null) checkShorter(n,w); return; } map[p.getX()][p.getY()] = true; //n.Print(); loop(n); } public void go(String path) { try { Scanner in = new Scanner(new FileReader(path)); int n = in.nextInt(); int i_start = in.nextInt(); int j_start = in.nextInt(); int i_end = in.nextInt(); int j_end = in.nextInt(); printShortestPath(n, i_start, j_start, i_end, j_end); in.close(); } catch (Exception ex) { ex.printStackTrace(); } } static void determinePossible(innerObj obj) { Pos p = obj.getPos(); List dl = obj.getPossible(); Dirs l = obj.getLabel(); Dirs ops = null; if (l != null) ops = dmap.get(l); if ((l == null) || ((ops != null) && (ops != Dirs.UL))) { Pos ul = Ul(p); if (valid(ul)) dl.add(Dirs.UL); } if ((l == null) || ((ops != null) && (ops != Dirs.UR))) { Pos ur = Ur(p); if (valid(ur)) dl.add(Dirs.UR); } if ((l == null) || ((ops != null) && (ops != Dirs.R))) { Pos r = R(p); if (valid(r)) dl.add(Dirs.R); } if ((l == null) || ((ops != null) && (ops != Dirs.LR))) { Pos lr = Lr(p); if (valid(lr)) dl.add(Dirs.LR); } if ((l == null) || ((ops != null) && (ops != Dirs.LL))) { Pos ll = Ll(p); if (valid(ll)) dl.add(Dirs.LL); } if ((l == null) || ((ops != null) && (ops != Dirs.L))) { Pos lp = L(p); if (valid(lp)) dl.add(Dirs.L); } } static boolean valid(Pos p) { if (p.getX() < 0) return false; if (p.getY() < 0) return false; if (p.getX() >= bsize) return false; if (p.getY() >= bsize) return false; if (map[p.getX()][p.getY()]) return false; return true; } static Pos Ul(Pos p) { Pos ret = new Pos(); ret.x = p.getX() -1; ret.y = p.getY() -2; return ret; } static Pos Ur(Pos p) { Pos ret = new Pos(); ret.x = p.getX() +1; ret.y = p.getY() -2; return ret; } static Pos R(Pos p) { Pos ret = new Pos(); ret.x = p.getX() +2; ret.y = p.getY(); return ret; } static Pos Lr(Pos p) { Pos ret = new Pos(); ret.x = p.getX() +1; ret.y = p.getY() +2; return ret; } static Pos Ll(Pos p) { Pos ret = new Pos(); ret.x = p.getX() -1; ret.y = p.getY() +2; return ret; } static Pos L(Pos p) { Pos ret = new Pos(); ret.x = p.getX() -2; ret.y = p.getY(); return ret; } static enum Dirs { UL, UR, R, LR, LL, L }; static class Pos { private int x; private int y; public Pos(innerObj obj,Dirs d) { x = obj.getPos().getX(); y = obj.getPos().getY(); } public Pos() { /* nop */ } public Pos(int ix,int iy) { x = ix; y = iy; } public void setX(int ix) { x = ix; } public void setY(int iy) { y = iy; } public int getX() { return x; } public int getY() { return y; } } static class wtmp { private int length; private Winner winner = null; private innerObj obj = null; public wtmp(int l,Winner w,innerObj o) { length = l; winner = w; obj = o; } public int getLength() { return winner.getLength() - length; } public Winner getWinner() { return winner; } public innerObj getObj() { return obj; } public void Print() { System.out.println("Length: " + length); obj.Print(); System.out.println("WLength: " + winner.getLength()); } } static class Winner { private int length = 0; private List path = null; public Winner(innerObj obj) { length = 0; path = new Vector(); determinePath(obj); } public int getLength() { return length; } public List getPath() { return path; } private void merge(Winner w,wtmp wt) { int l = wt.getLength(); Winner tw = wt.getWinner(); List m = tw.rest(l); path.addAll(m); length += m.size(); } public List rest(int idx) { List ret = new Vector(); int i = 0; for (i=idx;i tpath = new Vector(); innerObj tmp = obj; while (tmp != null) { if (tmp.getLabel() != null) { Pos p = tmp.getPos(); wtmp w = new wtmp(length,this,tmp); rmap[p.getX()][p.getY()] = w; tpath.add(tmp); length++; } tmp = tmp.getParent(); } int i = 0; for (i=tpath.size()-1;i>=0;i--) { innerObj o = tpath.get(i); path.add(o); } } public void Print() { System.out.println(length); String pstr = null; for (innerObj d : path) if (pstr == null) pstr = d.getLabel().toString(); else pstr = pstr + " " + d.getLabel().toString(); System.out.println(pstr); } } static class innerObj { private Dirs label = null; private Pos pos; private List possible; private innerObj parent = null; public innerObj(innerObj obj,Dirs d) { parent = obj; label = d; possible = new Vector(); nPos(obj,d); } public void Print() { String pstr = ""; if (label != null) pstr = pstr.concat("Label: " + label + " "); if (parent != null) { Pos p = parent.getPos(); pstr = pstr.concat("X: " + pos.getX() + " Y: " + pos.getY() + " PX: " + p.getX() + " PY: " + p.getY()); } else pstr = pstr.concat("X: " + pos.getX() + " Y: " + pos.getY()); System.out.println(pstr); } private void nPos(innerObj obj,Dirs d) { Pos p = obj.getPos(); if (d == Dirs.UL) pos = Ul(p); if (d == Dirs.UR) pos = Ur(p); if (d == Dirs.R) pos = R(p); if (d == Dirs.LL) pos = Ll(p); if (d == Dirs.LR) pos = Lr(p); if (d == Dirs.L) pos = L(p); } public innerObj(int x,int y) { possible = new Vector(); pos = new Pos(x,y); } public innerObj getParent() { return parent; } public void setParent(innerObj o) { parent = o; } public Dirs getLabel() { return label; } public void setLabel(Dirs l) { label = l; } public Pos getPos() { return pos; } public List getPossible() { return possible; } } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int i_start = in.nextInt(); int j_start = in.nextInt(); int i_end = in.nextInt(); int j_end = in.nextInt(); printShortestPath(n, i_start, j_start, i_end, j_end); in.close(); } }