import java.io.*; import java.util.*; public class Maze { static class Configuration implements Comparable { int x; int y; Configuration last; char move; int f, c, h; // c() is g() is the lecture notes, the current cost static int now = 0; Configuration() { this.last = null; } public int calcF() { h = 0; h = Math.abs(goal.x - x) + Math.abs(goal.y - y); return f = c + h; } public int compareTo(Object other) { // Priority Queue needs this // method Configuration that = (Configuration) other; return this.f - that.f; } public boolean equals(Object other) { Configuration that = (Configuration) other; if (this.x != that.x || this.y != that.y) return false; return true; } public int hashCode() { // HashSet needs this method int result = x * 13 + y * 19; return result; } public char current() { return map[y].charAt(x); } public boolean isFinished(Configuration goal) { if (this.x == goal.x && this.y == goal.y) return true; else return false; } public void printPath() { if (last != null) { last.printPath(); System.out.print(move); /* * System.out.println(); char[] row = map[y].toCharArray(); * row[x] = 'R'; map[y] = new String(row); for (int i=0; i visited = new HashSet(); // LinkedList queue = new LinkedList(); PriorityQueue Q = new PriorityQueue(); Q.add(conf); visited.add(conf); // queue.addLast(conf); int nnodes = 1; while (Q.peek() != null) { // queue.isEmpty()) { // conf = (Configuration) queue.removeFirst(); conf = (Configuration) Q.poll(); if (conf.isFinished(goal)) break; for (int i = 0; i < moves.length; i++) { Configuration next = move(conf, dX[i], dY[i], moves[i]); if (next != null && !visited.contains(next)) { nnodes++; next.calcF(); visited.add(next); // queue.addLast(next); Q.add(next); } } } conf.printPath(); System.out.println(); System.out.println(); System.out.println("# of nodes generated: " + nnodes); } static Configuration move(Configuration source, int dx, int dy, char move) { Configuration result = new Configuration(); result.x = source.x + dx; result.y = source.y + dy; result.last = source; result.move = move; result.c = source.c + 1; if (result.x >= 0 && result.x <= height && result.y >= 0 && result.y < width) { if (result.current() != '#') return result; else return null; } else return null; } } /* input: 16 18 #### ## #### # ######## # # # #### ### #### # # # # # # # # # # # # # # # # ## @ # # # ## ## # # # # ### .# ## # # # ### # # # # # ## # # ### # # # # ###### ##### @ is the MAN . is the GOAL output: wwsssssswwnnnn # of nodes generated: 68 */