Knight_game_Samsung

#include <iostream>
using namespace std;

class que{
    int row[1000];
    int col[1000];
    int front,rear;
    public:
        que(){
            front=rear=0;
        }
        void push(int x, int y){
            row[rear]=x;
            col[rear]=y;
            rear++;
        }
        void top(int &x, int &y){
            x=row[front];
            y=col[front];
        }
        void pop(){
            front++;
        }
        bool empty(){
            return front==rear;
        }
        int size(){
            return rear-front;
        }
};

int r,c;
int s1,s2,d1,d2;

bool valid(int x, int y, bool visited[100][100]){
    if(x>=0 && x<r && y>=0 && y<c && visited[x][y]==false)
        return true;
    return false;
}

int bfs(int s1, int s2, int d1, int d2){
    bool visited[100][100]={false};

    int distance[1000][1000];
    for(int i=0; i<1000; i++)
        for(int j=0; j<1000; j++)
            distance[i][j]=-1;

    que q;
    q.push(s1,s2);
    visited[s1][s2]=true;
    distance[s1][s2]=0;

    while(!q.empty()){
        int x, y;
        q.top(x,y);
        q.pop();

        int dx[]={1,2,2,1,-1,-2,-2,-1};
        int dy[]={2,1,-1,-2,-2,-1,1,2};

        for(int i=0; i<8; i++){
            int m=x+dx[i];
            int n=y+dy[i];

            if(valid(m,n,visited)){
                q.push(m,n);
                visited[m][n]=true;
                distance[m][n] = distance[x][y] + 1;
            }
        }
    }
    return distance[d1][d2];
}

int main() {
    int t;
    cin>>t;
    while(t--){
        cin>>r>>c;

        cin>>s1>>s2>>d1>>d2;
        cout<<bfs(s1-1,s2-1,d1-1,d2-1)<<endl;
    }
}