Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- public class ShortestPath {
- Point[][] grid;
- public static void main(String[] args){
- new ShortestPath().doMain(args);
- }
- void doMain(String[] args) {
- if (args==null || args.length < 2)
- args = new Scanner(System.in).nextLine().split(" ");
- int size = Integer.parseInt(args[0]);
- grid = new Point[size][size];
- Point start = null, end = null;
- for (int i=0; i<grid.length; i++){
- for(int j=0; j<grid[i].length; j++){
- grid[i][j] = new Point(i, j, args[i+1].charAt(j));
- if (grid[i][j].c == 'S') start = grid[i][j];
- if (grid[i][j].c == 'E') end = grid[i][j];
- }
- }
- System.out.println(aStar(start, end).toStringAndDrawPath(grid));
- }
- private Path aStar(Point start, Point end) {
- PriorityQueue<Path> q = new PriorityQueue<Path>();
- Set<Point> closed = new HashSet<Point>();
- Path path = new Path(start);
- q.add(path);
- while (!q.isEmpty()) {
- path = q.poll();
- Point curPoint = path.points.getLast();
- if (curPoint.equals(end)) return path;
- if (closed.contains(curPoint)) continue;
- closed.add(curPoint);
- for (Point point: getNeighbours(curPoint)) {
- Path newPath = new Path(path);
- newPath.points.addLast(point);
- newPath.heuristicCost = heuristic(point, end);
- q.add(newPath);
- }
- }
- return new Path();
- }
- int heuristic(Point from, Point to) {
- return Math.abs(to.i - from.i) + Math.abs(to.j - from.j);
- }
- public Set<Point> getNeighbours(Point p) {
- int i = p.i, j = p.j;
- Set<Point> neighbours = new HashSet<Point>();
- for (int m = Math.max(i - 1, 0); m <= Math.min(i + 1, grid.length - 1); m++)
- if (grid[m][j].c != 'W') neighbours.add(grid[m][j]);
- for (int n = Math.max(j - 1, 0); n <= Math.min(j + 1, grid[0].length - 1); n++)
- if (grid[i][n].c != 'W') neighbours.add(grid[i][n]);
- return neighbours;
- }
- }
- class Point {
- int i, j;
- char c;
- public Point (int i, int j, char c) {
- this.i = i;
- this.j = j;
- this.c = c;
- }
- }
- class Path implements Comparable<Path> {
- Deque<Point> points = new ArrayDeque<Point>();
- int heuristicCost = 0;
- public Path(Point point){
- points.addLast(point);
- }
- /** Create a clone of the current path p */
- public Path(Path p) {
- points = new ArrayDeque<Point>(p.points);
- }
- public Path(){}
- @Override
- public int compareTo(Path path2) {
- return Integer.compare(points.size() + heuristicCost,
- path2.points.size() + path2.heuristicCost);
- }
- @Override
- public String toString() {
- if (points.size()==0) return "False";
- return "True, " + (points.size()-1);
- }
- public String toStringAndDrawPath(Point[][] inputGrid) {
- if (points.size()==0) return "False";
- String result = toString() + "\n\n";
- char[][] map = new char[inputGrid.length][inputGrid.length];
- for (int i=0; i<map.length; i++)
- for (int j=0; j<map.length; j++)
- map[i][j] = inputGrid[i][j].c;
- for (Point p: points)
- if (p.c != 'S' && p.c != 'E') map[p.i][p.j] = '-';
- for (char[] row: map) {
- result += new String(row) + "\n";
- }
- return result;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement