Rook

public class Solution {

    static int x_dir[];
    static int y_dir[];

    static class Pair
    {
        int x;
        int y;
        int dir;
        int step;

        public Pair(int x,int y,int dir,int step)
        {
            this.x=x;
            this.y=y;
            this.dir=dir;
            this.step=step;
        }
    }

    public static boolean check(int a[][],int x,int y,int n,int m)
    {
        if(x<0 || y<0 || x>=n  || y>=m) return false;
        if(a[x][y]==1) return false;
        return true;
    }

    public int solve(int A, int B, int C, int D, ArrayList<String> E) {

        x_dir=new int[]{0,0,1,-1};
        y_dir=new int[]{1,-1,0,0};

        A--; B--; C--; D--;

        int a[][]=new int[E.size()][E.get(0).length()];
        int dist[][]=new int[E.size()][E.get(0).length()];

        for(int i=0;i<E.size();i++)
        {
            for(int j=0;j<E.get(i).length();j++)
            {
              a[i][j]=Character.getNumericValue(E.get(i).charAt(j));
              dist[i][j]=Integer.MAX_VALUE;
            }
        }

        LinkedList<Pair> qu=new LinkedList<Pair>();
        qu.add(new Pair(A,B,-1,1));

        while(!qu.isEmpty())
        {
            Pair p=qu.pollFirst();
            int cur_x=p.x;
            int cur_y=p.y;
            int cur_dir=p.dir;
            int cur_step=p.step;

            if(dist[cur_x][cur_y]<cur_step) continue;

            dist[cur_x][cur_y]=cur_step;

            for(int k=0;k<4;k++)
            {
                int new_x=cur_x+x_dir[k];
                int new_y=cur_y+y_dir[k];

                if(check(a,new_x,new_y,a.length,a[0].length))
                {
                    if(cur_dir==-1)
                    {
                        qu.add(new Pair(new_x,new_y,k,cur_step));
                    }
                    else
                    {
                        if(k==cur_dir)
                           qu.add(new Pair(new_x,new_y,k,cur_step));
                        else
                           qu.add(new Pair(new_x,new_y,k,cur_step+1));
                    }
                }
            }
        }

        if(dist[C][D]!=Integer.MAX_VALUE) return dist[C][D];

        return -1;

    }
}