// this version illustrates use of Dijkstra's shortest-path algorithm // and uses the built-in Java PriorityQueue class import java.util.Scanner; import java.util.Comparator; import java.util.PriorityQueue; class City { // main procedure public static void main (String Scanner[]) { Scanner inScan = new Scanner (System.in); int n; // number of rows, columns int start; int dest; int V; // number of nodes = n * n - 1 // read in the problem n = inScan.nextInt (); V = n * n - 1; start = inScan.nextInt (); dest = inScan.nextInt (); // System.out.println("start = " + start + // " dest = " + dest); // create the neighbor structure // this is a specialized adjacency list int[][] neighbor = new int[V+1][4]; for (int i = 0; i < V; i++) for (int j = 0; j < 4; j++) neighbor[i][j] = -1; for (int x = 0; x < V; x++) { switch (x % 4) { case 0: if (x-n >= 0) neighbor[x][0] = x-n; // north if (x+n < V) neighbor[x][1] = x+n; // south if ((x-n >= 0) && (x % n > 0)) neighbor[x][2] = x-n-1; // nw if ((x-n >= 0) && (x % n < n-1)) neighbor[x][3] = x-n+1; // ne break; case 1: if ((x-n >= 0) && (x % n < n-1)) neighbor[x][0] = x-n+1; // ne if ((x+n < V) && (x % n > 0)) neighbor[x][1] = x+n-1; // sw if (x % n < n-1) neighbor[x][2] = x+1; // east break; case 2: if (x % n > 0) neighbor[x][0] = x-1; // west if (x % n < n-1) neighbor[x][1] = x+1; // east if ((x+n < V) && (x % n > 0)) neighbor[x][2] = x+n-1; // sw if ((x+n < V) && (x % n < n-1)) neighbor[x][3] = x+n+1; // se break; case 3: if ((x-n >= 0) && (x % n > 0)) neighbor[x][0] = x-n-1; // nw if ((x+n < V) && (x % n < n-1)) neighbor[x][1] = x+n+1; // se if (x % n > 0) neighbor[x][2] = x-1; // west } } // create and initialize the distance array final int[] d = new int[V+1]; for (int i = 0; i < V; i++) d[i] = Integer.MAX_VALUE; d[start] = 0; // create and initialize the set of settled nodes boolean[] settled = new boolean[V+1]; for (int i = 0; i < V; i++) settled[i] = false; // create the return path int[] path = new int[V+1]; for (int i = 0; i < V; i++) path[i] = -1; // find shortest path using Dijkstra's algorithm Comparator shortestDistance = new Comparator() { public int compare(Integer L, Integer R) { if (d[L] > d[R]) return 1; if (d[L] < d[R]) return -1; if (L > R) return 1; if (L < R) return -1; return 0; } }; PriorityQueue q = // unsettled nodes new PriorityQueue(V, shortestDistance); // put all the nodes into the queue for (int i = 0; i < V; i++) q.add(i); while (! q.isEmpty()) { int x = q.poll(); // extracts minimum if (x == dest) break; settled[x] = true; // "relax" neighbors for (int i = 0; i < 4; i++) { int y = neighbor[x][i]; // for each vertex y adjacent to x, not in s if ((y != -1) && ! settled[y]) { if ((d[y] > d[x] + 1)) { d[y] = d[x] + 1; path[y] = x; q.remove(y); q.add(y); } } } } if (d[dest] == Integer.MAX_VALUE) System.out.println("no path!"); else { // System.out.println("distance = " + d[dest]); // find a path of minimum length // reverse the path int x = dest; int px = path[x]; while (x != start) { int ppx = path[px]; path[px] = x; x = px; px = ppx; } // now print it out x = start; while (x != dest) { System.out.print(x + " "); x = path[x]; } System.out.println(x); } } }