import java.util.*; /**  * Created by wxn  * 2019/9/3 19:02  * <p>  * 题目描述：  * 假设以一个n*m的矩阵作为棋盘，每个棋位对应一个二维坐标 (x, y)。你有一颗棋子位于左上起点(0, 0)，现在需要将其移动到右下底角 (n-1, m-1)，棋子可以向相邻的上下左右位置移动，每个坐标最多只能经过一次。棋盘中散布着若干障碍，障碍物不能跨越，只能绕行，问是否存在到达右下底角的路线？若存在路线，输出所需的最少移动次数；若不存在，输出0。 Input 第一行三个正整数n，m和k，代表棋盘大小与障碍物个数  1< n、m < 100,  k < n*m 第二行至第k+1行，每行为两个整数x和y，代表k个障碍物的坐标。  * <p>  * 输入  * 输入三个正整数n，m和k，代表棋盘大小与障碍物个数  1< n、m < 100,  k < n*m  * <p>  * 第二行至第k+1行，每行为两个整数x和y，代表k个障碍物的坐标。  * <p>  * 输出  * 输出从起点到终点的最短路径的长度，如果不存在，即输出0  */ public class Main { static int[][] d = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} }; static int startX = 0; static int startY = 0; static int endX = 0; static int endY = 0; static Set<Integer> stepList = new HashSet<>(); public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); in.nextLine(); //棋盘,障碍物为1,否则为0 /**  * 5  * .#...  * ..#S.  * .E###  * .....  * .....  */ char[][] board = new char[n][n]; for (int i = 0; i < n; i++) { String line = in.nextLine(); for (int j = 0; j < n; j++) { board[i][j] = line.charAt(j); if (board[i][j] == 'S') { startX = i; startY = j; } else if (board[i][j] == 'E') { endX = i; endY = j; } } } shortestLength(board, n); if (stepList.size() == 0) { System.out.println(-1); return; } int minStep = Integer.MAX_VALUE; for (Integer integer : stepList) { if (integer < minStep) { minStep = integer; } } System.out.println(minStep); } private static void shortestLength(char[][] board, int n) { boolean[][] visited = new boolean[n][n]; visited[startX][startY] = true; shortestLength(board, n, startX, startY, 0, visited); } private static void shortestLength(char[][] board, int n, int startX, int startY, int step, boolean[][] visited) { if (startX == endX && startY == endY) { stepList.add(step); return; } for (int i = 0; i < 4; i++) { int newX = startX + d[i][0]; int newY = startY + d[i][1]; if (newX < 0) { newX = n - 1; } else if (newX==n) { newX = 0; } if (newY <0) { newY = n-1; }else if (newY==n){ newY = 0; } if (board[newX][newY] !='#' && !visited[newX][newY]) { visited[newX][newY] = true; shortestLength(board, n, newX, newY, step + 1, visited); visited[newX][newY] = false; } } } }