/* * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. */ /** * * @author dipankar12 */ import java.io.*; import java.util.*; public class rkspath { int i,j; void printpath(ArrayList> path) { //System.out.println(path); if(path.size()==0) { System.out.println("Impossible"); return; } HashMap hm=new HashMap(); hm.put("UL", 1); hm.put("UR", 2); hm.put("R", 3); hm.put("LR", 4); hm.put("LL", 5); hm.put("L", 6); int min=Integer.MAX_VALUE; String str=""; String str1=""; for(int i=0;i path1=path.get(i); int p=0,q=0; for(int j=0;j path1=path.get(i); int p=0,q=0; for(int j=0;jhm.get(st1[j])) { str=str1; break; } } } str1=""; } } String st[]=str.split(" "); System.out.println(st.length); for(int i=0;i al=new ArrayList(); ArrayList> path=new ArrayList>(); ArrayList> path2=new ArrayList>(); ArrayList path1=new ArrayList(); boolean visited[][]=new boolean[201][201]; //System.out.println(visited1[0]); al.add(src); visited[src.i][src.j]=true; ArrayList path3=new ArrayList(); path3.add(src); path.add(path3); //System.out.println("path1 is"+path1+" path is "+path1); while(!al.isEmpty()) { rkspath ob=al.get(0); //System.out.println("path is"+path); //System.out.println("ob now is"+ob.i+" "+ob.j+" "+ob); al.remove(ob); for(int k=0;k=0&&ob.j-1>=0&&!visited[ob.i-2][ob.j-1]) { //System.out.println("Checking for"+(ob.i-2)+" "+(ob.j-1)+" "+visited[ob.i-2][ob.j-1]); rkspath ob1=new rkspath(); ob1.i=ob.i-2; ob1.j=ob.j-1; visited[ob.i-2][ob.j-1]=true; al.add(ob1); //if(ob.i==src.i&&ob.j==src.j) //{ //ArrayList y=new ArrayList(); //y.add(ob1); //path.add(y); //} //else //{ ArrayList y=new ArrayList(); y.addAll(path1); y.add(ob1); path.add(y); //} //System.out.println("path1 is"+path1); if(isdest(ob1,dest)) { visited[dest.i][dest.j]=false; if(count>path.get(path.size()-1).size()) { path2.clear(); path2.add(path.get(path.size()-1)); count=path.get(path.size()-1).size(); } else if(count==path.get(path.size()-1).size()) { path2.add(path.get(path.size()-1)); count=path.get(path.size()-1).size(); } } } if(ob.i-2>=0&&ob.j+1 y=new ArrayList(); //y.add(ob1); //path.add(y); //} //else //{ ArrayList y=new ArrayList(); y.addAll(path1); y.add(ob1); path.add(y); //} //System.out.println("path1 is"+path1); if(isdest(ob1,dest)) { visited[dest.i][dest.j]=false; if(count>path.get(path.size()-1).size()) { path2.clear(); path2.add(path.get(path.size()-1)); count=path.get(path.size()-1).size(); } else if(count==path.get(path.size()-1).size()) { path2.add(path.get(path.size()-1)); count=path.get(path.size()-1).size(); } } } if(ob.j-2>=0&&!visited[ob.i][ob.j-2]) { //System.out.println("Checking for"+(ob.i)+" "+(ob.j-2)+" "+visited[ob.i][ob.j-2]); rkspath ob1=new rkspath(); ob1.i=ob.i; ob1.j=ob.j-2; visited[ob.i][ob.j-2]=true; al.add(ob1); //if(ob.i==src.i&&ob.j==src.j) //{ //ArrayList y=new ArrayList(); //y.add(ob1); //path.add(y); //} //else //{ ArrayList y=new ArrayList(); y.addAll(path1); y.add(ob1); path.add(y); //} //System.out.println("path1 is"+path1); if(isdest(ob1,dest)) { visited[dest.i][dest.j]=false; if(count>path.get(path.size()-1).size()) { path2.clear(); path2.add(path.get(path.size()-1)); count=path.get(path.size()-1).size(); } else if(count==path.get(path.size()-1).size()) { path2.add(path.get(path.size()-1)); count=path.get(path.size()-1).size(); } } } if(ob.j+2 y=new ArrayList(); //y.add(ob1); //path.add(y); //} //else //{ ArrayList y=new ArrayList(); y.addAll(path1); y.add(ob1); path.add(y); //} //System.out.println("path1 is"+path1); if(isdest(ob1,dest)) { visited[dest.i][dest.j]=false; if(count>path.get(path.size()-1).size()) { path2.clear(); path2.add(path.get(path.size()-1)); count=path.get(path.size()-1).size(); } else if(count==path.get(path.size()-1).size()) { path2.add(path.get(path.size()-1)); count=path.get(path.size()-1).size(); } } } if(ob.i+2=0&&!visited[ob.i+2][ob.j-1]) { //System.out.println("Checking for"+(ob.i+2)+" "+(ob.j-1)+" "+visited[ob.i+2][ob.j-1]); rkspath ob1=new rkspath(); ob1.i=ob.i+2; ob1.j=ob.j-1; visited[ob.i+2][ob.j-1]=true; al.add(ob1); //if(ob.i==src.i&&ob.j==src.j) //{ //ArrayList y=new ArrayList(); //y.add(ob1); //path.add(y); //} //else //{ ArrayList y=new ArrayList(); y.addAll(path1); y.add(ob1); path.add(y); //} //System.out.println("path1 is"+path1); if(isdest(ob1,dest)) { visited[dest.i][dest.j]=false; if(count>path.get(path.size()-1).size()) { path2.clear(); path2.add(path.get(path.size()-1)); count=path.get(path.size()-1).size(); } else if(count==path.get(path.size()-1).size()) { path2.add(path.get(path.size()-1)); count=path.get(path.size()-1).size(); } } } if(ob.i+2 y=new ArrayList(); //y.addAll(path1); //path.add(y); //} //else //{ ArrayList y=new ArrayList(); y=path1; y.addAll(path1); y.add(ob1); path.add(y); //} //System.out.println("path1 is"+path1); if(isdest(ob1,dest)) { visited[dest.i][dest.j]=false; if(count>path.get(path.size()-1).size()) { path2.clear(); path2.add(path.get(path.size()-1)); count=path.get(path.size()-1).size(); } else if(count==path.get(path.size()-1).size()) { path2.add(path.get(path.size()-1)); count=path.get(path.size()-1).size(); } } } } printpath(path2); } public static void main(String args[]) { fastio in=new fastio(System.in); PrintWriter pw=new PrintWriter(System.out); int n=in.nextInt(); int is=in.nextInt(); int js=in.nextInt(); int ie=in.nextInt(); int je=in.nextInt(); rkspath ob=new rkspath(); ob.i=is; ob.j=js; rkspath ob1=new rkspath(); ob1.i=ie; ob1.j=je; rkspath ob2=new rkspath(); ob2.path(ob, ob1, n); } static class fastio { private final InputStream stream; private final byte[] buf = new byte[8192]; private int cchar, snchar; private SpaceCharFilter filter; public fastio(InputStream stream) { this.stream = stream; } public int nxt() { if (snchar == -1) throw new InputMismatchException(); if (cchar >= snchar) { cchar = 0; try { snchar = stream.read(buf); } catch (IOException e) { throw new InputMismatchException(); } if (snchar <= 0) return -1; } return buf[cchar++]; } public int nextInt() { int c = nxt(); while (isSpaceChar(c)) { c = nxt(); } int sgn = 1; if (c == '-') { sgn = -1; c = nxt(); } int res = 0; do { if (c < '0' || c > '9') throw new InputMismatchException(); res *= 10; res += c - '0'; c = nxt(); } while (!isSpaceChar(c)); return res * sgn; } public long nextLong() { int c = nxt(); while (isSpaceChar(c)) { c = nxt(); } int sgn = 1; if (c == '-') { sgn = -1; c = nxt(); } long res = 0; do { if (c < '0' || c > '9') throw new InputMismatchException(); res *= 10; res += c - '0'; c = nxt(); } while (!isSpaceChar(c)); return res * sgn; } public int[] nextIntArray(int n) { int a[] = new int[n]; for (int i = 0; i < n; i++) { a[i] = nextInt(); } return a; } public String readString() { int c = nxt(); while (isSpaceChar(c)) { c = nxt(); } StringBuilder res = new StringBuilder(); do { res.appendCodePoint(c); c = nxt(); } while (!isSpaceChar(c)); return res.toString(); } public String nextLine() { int c = nxt(); while (isSpaceChar(c)) c = nxt(); StringBuilder res = new StringBuilder(); do { res.appendCodePoint(c); c = nxt(); } while (!isEndOfLine(c)); return res.toString(); } public boolean isSpaceChar(int c) { if (filter != null) return filter.isSpaceChar(c); return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } private boolean isEndOfLine(int c) { return c == '\n' || c == '\r' || c == -1; } public interface SpaceCharFilter { public boolean isSpaceChar(int ch); } } }