import java.util.*;

public class ShortestPath {
    private static Map map = new Map();
    private static Character[][] modifiedMap = map.getMap();
    private static boolean[][] visited = new boolean[Map.HEIGHT][Map.WIDTH];

    public static int getCoordinateX(String coordinate){
        String x = coordinate.substring(0, 2);
        int coor = (x.charAt(0) - 'A') * 10 + Character.getNumericValue(x.charAt(1));
        return coor;
    }

    public static int getCoordinateY(String coordinate){
        String y = coordinate.substring(2, 4);
        int coor = (y.charAt(0) - 'Q')  * 10 + Character.getNumericValue(y.charAt(1));
        return coor;
    }

    public static int calculateDistance(String from, String to){
        int xStart = getCoordinateX(from);
        int xEnd = getCoordinateX(to);
        int yStart = getCoordinateY(from);
        int yEnd = getCoordinateY(to);

        int dist = 0;
        Point p = getPathBFS(xStart, yStart, xEnd, yEnd);
        while(p.getParent() != null) {
            modifiedMap[p.x][p.y] = '.';
            dist++;
            p = p.getParent();
        }
        modifiedMap[xEnd][yEnd] = 'F';
        printModifiedMap();
        System.out.println(dist);
        return dist;
    }

    private static class Point {
        int x;
        int y;
        Point parent;

        public Point(int x, int y, Point parent) {
            this.x = x;
            this.y = y;
            this.parent = parent;
        }

        public Point getParent() {
            return this.parent;
        }
    }

    public static Queue<Point> q = new LinkedList<Point>();
    public static Point getPathBFS(int x, int y, int xEnd, int yEnd) {
        for (int i=0;i<Map.HEIGHT;++i){
        	for (int j=0;j<Map.WIDTH;++j){
        		visited[i][j]=false;
        	}
        }
        q.add(new Point(x,y, null));

        modifiedMap[xEnd][yEnd] = 'F';
        visited[x][y] = true;
        modifiedMap[x][y] = 'S';
        while(!q.isEmpty()) {
            Point p = q.remove();
            if (modifiedMap[p.x][p.y] == 'F') {
                System.out.println("Exit is reached!");
                return p;
            }

            if(isFree(p.x+1,p.y)) {
                Point nextP = new Point(p.x+1,p.y, p);
                visited[nextP.x][nextP.y] = true;
                q.add(nextP);
            }

            if(isFree(p.x-1,p.y)) {
                Point nextP = new Point(p.x-1,p.y, p);
                visited[nextP.x][nextP.y] = true;
                q.add(nextP);
            }

            if(isFree(p.x,p.y+1)) {
                Point nextP = new Point(p.x,p.y+1, p);
                visited[nextP.x][nextP.y] = true;
                q.add(nextP);
            }

            if(isFree(p.x,p.y-1)) {
                Point nextP = new Point(p.x,p.y-1, p);
                visited[nextP.x][nextP.y] = true;
                q.add(nextP);
            }

        }
        return null;
    }

    public static boolean isFree(int x, int y) {
        if((x >= 0 && x < Map.HEIGHT) && (y >= 0 && y < Map.WIDTH)
                && (modifiedMap[x][y] == ' ' || modifiedMap[x][y] == 'F') && (!visited[x][y])) {
            return true;
        }
        return false;
    }

    public static void printModifiedMap(){
        map.print();
    }

}