import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static class Cell { int row; int col; int dist; String prevStep; Cell prevCell; boolean visited; public Cell(int c, int r) { visited = false; col = c; row = r; prevStep = null; prevCell = null; dist = 0; } } static boolean isInside(int x, int y, int n) { if ((x>=0) && (x=0) && (y q = new LinkedList(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cList[i][j] = new Cell(j, i); } } q.add(cList[r_start][c_start]); while (!q.isEmpty()) { t = q.poll(); t.visited = true; // if reached end if ((t.row == r_end) && (t.col == c_end)) { System.out.println(t.dist); // print out all the steps etc... TO DO: Cell p = t; ArrayList result = new ArrayList(); while (p.prevStep != null) { result.add(p.prevStep); p = p.prevCell; } for (int i = result.size() - 1; i >= 0; i--) { System.out.print(result.get(i) + " "); } /* for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { System.out.print(cList[i][j].dist + " "); } System.out.println(); } */ return; } // explore all possible options for (int i = 0; i < 6; i++) { c = t.col + dc[i]; r = t.row + dr[i]; d = dir[i]; if (isInside(c,r,n) && !(cList[r][c].visited)) { Cell tmp = cList[r][c]; tmp.dist = (t.dist + 1); tmp.prevStep = d; tmp.prevCell = t; tmp.visited = true; q.add(tmp); } } } System.out.println("Impossible"); } 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(); } }