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