import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { //start and end positions guarenteed to be different static void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { // Print the distance along with the sequence of moves. int[][] c = new int[n][n]; int[][] d = new int[n][n]; //i think the default value is null for(int i=0; i qi = new LinkedList(); Queue qj = new LinkedList(); Queue qc = new LinkedList(); Queue qd = new LinkedList(); push(i_start, j_start, 0, 0, qi, qj, qc, qd); while(!qi.isEmpty()){ int ni = qi.poll(); int nj = qj.poll(); int nc = qc.poll(); int nd = qd.poll(); fill(ni, nj, nc, nd, c, d, qi, qj, qc, qd); } /*for(int i=0; i res = new ArrayList(); int i = i_end; int j = j_end; ////UL, UR, R, LR, LL, L while(i != i_start || j != j_start){ int dir = d[i][j]; if(dir == 1){ res.add("UL"); i+=2; j+=1; } else if(dir == 2){ res.add("UR"); i+=2; j-=1; } else if(dir == 3){ res.add("R"); j-=2; } else if(dir == 4){ res.add("LR"); i-=2; j-=1; } else if(dir == 5){ res.add("LL"); i-=2; j+=1; } else { if(dir != 6) throw new RuntimeException(); res.add("L"); j+=2; } } Collections.reverse(res); //System.out.println(res); for(int r=0; r qi, Queue qj, Queue qc, Queue qd){ //if(i == si && j == sj) return; int n = c.length; if(i < 0 || j < 0 || i >= n || j >= n) return; /*if(c[i][j] == cost){ d[i][j] = Math.min(d[i][j], dir); } else */if(c[i][j] == -1){ c[i][j] = cost; d[i][j] = dir; push(i-2, j-1 , cost+1, 1, qi, qj, qc, qd); push(i-2 , j+1 , cost+1, 2, qi, qj, qc, qd); push(i , j+2 , cost+1, 3, qi, qj, qc, qd); push(i+2 , j+1 , cost+1, 4, qi, qj, qc, qd); push(i+2 , j-1 , cost+1, 5, qi, qj, qc, qd); push(i , j-2 , cost+1, 6, qi, qj, qc, qd); } //else do nothing; } static void push(int i, int j, int c, int d, Queue qi, Queue qj, Queue qc, Queue qd){ qi.add(i); qj.add(j); qc.add(c); qd.add(d); } 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(); } }