import java.util.*;

class Position2D {
    int x;
    int y;
    Position2D(int x, int y){
        this.x = x;
        this.y = y;
    }
    public boolean equals(Object obj){
        return obj instanceof Position2D
                && (((Position2D)obj).x == this.x)
                &&(((Position2D)obj).y == this.y);
    }
}

class Config {

    Position2D horseA;
    Position2D horseB;

    char[][] record;
    int[][] isVisited;
    int stepUsed;

    Config(Position2D horseA, Position2D horseB, char[][] record, int[][] isVisited, int stepUsed){
        this.horseA = horseA;
        this.horseB = horseB;
        this.record = record;
        this.isVisited = isVisited;
        this.stepUsed = stepUsed;
    }
}
class Main12{

    public static void main(String[] args){
        char[][] record = {
                {'H','*','*','h','*'},
                {'*','*','h','*','*'},
                {'*','*','H','#','#'},
                {'#','#','*','*','*'},
                {'*','*','*','*','*'}
        };
        int[][] isVisited = new int[record.length][record[0].length];
        isVisited[0][0] = 1;
        isVisited[2][2] = 2;

        System.out.println(minimumJumps(new Position2D(0,0),new Position2D(2,2),
                new Position2D(3,0),new Position2D(2,1),record,isVisited,0));
    }


    static boolean isValid(char[][] record, Position2D ori, Position2D dest, Position2D another){
        //避免边界
        if(dest.x<0||dest.x>=record[0].length||dest.y<0||dest.y>=record.length) return false;
        //避免两马重合
        if(dest.equals(another)) return false;
        //避免障碍物
        if(record[dest.y][dest.x] == '#') return false;

//示意图： 蹩马腿情况示意图 共8种情况， 可以是另一只马（'H'）或者障碍物('#')
//  0 1 2 3 4 5 6 7 8 横坐标
//  1     1   3
//  2   2       4
//  3       m
//  4   5       8
//  5     6   7         //m可以抵达的位置
//纵坐标
        //case 2
        if(dest.y == ori.y - 1
                && dest.x == ori.x - 2
                && (record[ori.y-1][ori.x-1]=='#'||record[ori.y][ori.x-1]=='#'|| record[ori.y-1][ori.x-1]=='H'||record[ori.y][ori.x-1]=='H'))
            return false;
        //case 1
        if(dest.y == ori.y - 2
                && dest.x == ori.x - 1
                && (record[ori.y-1][ori.x]=='#'||record[ori.y-1][ori.x-1]=='#'|| record[ori.y-1][ori.x]=='H'||record[ori.y-1][ori.x-1]=='H'))
            return false;
        //case 5
        if(dest.y == ori.y + 1
                && dest.x == ori.x - 2
                && (record[ori.y+1][ori.x-1]=='#'||record[ori.y][ori.x-1]=='#'||record[ori.y+1][ori.x-1]=='H'||record[ori.y][ori.x-1]=='H'))
            return false;

        //case 6
        if(dest.y == ori.y + 2
                && dest.x == ori.x - 1
                && (record[ori.y+1][ori.x]=='#'||record[ori.y+1][ori.x-1]=='#'||record[ori.y+1][ori.x]=='H'||record[ori.y+1][ori.x-1]=='H'))
            return false;

        //case 3
        if(dest.y == ori.y - 2
                && dest.x == ori.x + 1
                && (record[ori.y-1][ori.x]=='#'||record[ori.y-1][ori.x+1]=='#'||record[ori.y-1][ori.x]=='H'||record[ori.y-1][ori.x+1]=='H'))
            return false;
        //case 4
        if(dest.y == ori.y - 1
                && dest.x == ori.x + 2
                && (record[ori.y-1][ori.x+1]=='#'||record[ori.y][ori.x+1]=='#'||record[ori.y-1][ori.x+1]=='H'||record[ori.y][ori.x+1]=='H'))
            return false;
        //case 8
        if(dest.y == ori.y + 1
                && dest.x == ori.x + 2
                && (record[ori.y][ori.x+1]=='#'||record[ori.y+1][ori.x+1]=='#'||record[ori.y][ori.x+1]=='H'||record[ori.y+1][ori.x+1]=='H'))
            return false;
        //case 7
        if(dest.y == ori.y + 2
                && dest.x == ori.x + 1
                && (record[ori.y+1][ori.x+1]=='#'||record[ori.y+1][ori.x]=='#'||record[ori.y+1][ori.x+1]=='H'||record[ori.y+1][ori.x]=='H'))
            return false;

        return true;

    }

    //可能的移动
    static int[][] possibleMove = {{-1,-2},{-2,-1},{1,-2},{2,-1},{-2,1},{-1,2},{1,2},{2,1}};

    //BFS Queue
    static Queue<Config> queue = new LinkedList<>();

    static int minimumJumps(Position2D horseA, Position2D horseB, Position2D d1, Position2D d2, char[][] record, int[][] isVisited, int stepUsed){

        queue.offer(new Config(horseA,horseB,record,isVisited,stepUsed));

        while(!queue.isEmpty()){

            Config current = queue.poll();

            for(int[] pm: possibleMove){
                horseA = current.horseA;
                horseB = current.horseB;
                record = current.record;
                isVisited = current.isVisited;
                stepUsed = current.stepUsed;

                Position2D destinationA = new Position2D(horseA.x+pm[0],horseA.y+pm[1]);
                if(!horseA.equals(d1)
                        &&isValid(record,horseA,destinationA,horseB)
                        &&isVisited[destinationA.y][destinationA.x]!=1&&isVisited[destinationA.y][destinationA.x]!=3){

                    char[][] newRecord =new char[record.length][record[0].length];
                    arrayCopy(record,newRecord);

                    newRecord[horseA.y][horseA.x] = '*';
                    newRecord[destinationA.y][destinationA.x] = 'H';

                    int[][] newIsVisited = new int[isVisited.length][isVisited[0].length];
                    arrayCopy(isVisited,newIsVisited);
                    newIsVisited[destinationA.y][destinationA.x]++;


                    if(newRecord[d1.y][d1.x] == 'H'&&newRecord[d2.y][d2.x] == 'H') return stepUsed + 1;

                    queue.offer(new Config(destinationA,horseB,newRecord,newIsVisited,stepUsed+1));
                }

                Position2D destinationB = new Position2D(horseB.x+pm[0],horseB.y+pm[1]);

                if(!horseB.equals(d2)
                        &&isValid(record,horseB,destinationB,horseA)&&
                        isVisited[destinationB.y][destinationB.x]!=2 && isVisited[destinationB.y][destinationB.x]!=3){

                    char[][] newRecord =new char[record.length][record[0].length];
                    arrayCopy(record,newRecord);

                    newRecord[horseB.y][horseB.x] = '*';
                    newRecord[destinationB.y][destinationB.x] = 'H';

                    int[][] newIsVisited = new int[isVisited.length][isVisited[0].length];
                    arrayCopy(isVisited,newIsVisited);
                    newIsVisited[destinationB.y][destinationB.x]+=2;

                    if(newRecord[d1.y][d1.x] == 'H'&&newRecord[d2.y][d2.x] == 'H') return stepUsed + 1;

                    queue.offer(new Config(horseA,destinationB,newRecord,newIsVisited,stepUsed+1));
                }

            }

        }
        return stepUsed+1;
    }

    public  static void arrayCopy(int[][] aSource, int[][] aDestination) {
        for (int i = 0; i < aSource.length; i++) {
            System.arraycopy(aSource[i], 0, aDestination[i], 0, aSource[i].length);
        }
    }
    public  static void arrayCopy(char[][] aSource, char[][] aDestination) {
        for (int i = 0; i < aSource.length; i++) {
            System.arraycopy(aSource[i], 0, aDestination[i], 0, aSource[i].length);
        }
    }
}