aStar

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;
    }

}