跳马

时限：1000ms 内存限制：10000K 总时限：3000ms

描述：

 

在国际象棋中，马的走法与中车象棋类似，即俗话说的“马走日”，下图所示即国际象棋中马（K）在一步能到达的格子（其中黑色的格子是能到达的位置）。

现有一200*200大小的国际象棋棋盘，棋盘中仅有一个马，给定马的当前位置（S）和目标位置（T），求出马最少需要多少跳才能从当前位置到达目标位置。

输入：

 

本题包含多个测例。输入数据的第一行有一个整数N（1<=N<=1000），表示测例的个数，接下来的每一行有四个以空格分隔的整数，分别表示马当前位置及目标位置的横、纵坐标C（x,y）和G（x,y）。坐标由1开始。

输出：

 

对于每个测例，在单独的一行内输出一个整数，即马从当前位置跳到目标位置最少的跳数。

输入样例：

 

2

1 1 2 1

1 5 5 1

输出样例：

 

3

4

 

/* * @author Panos */#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                //#include
                
                 #include
                 
                  using namespace std;#define DBG 1#define fori(i,a,b) for(int i = (a); i < (b); i++)#define forie(i,a,b) for(int i = (a); i <= (b); i++)#define ford(i,a,b) for(int i = (a); i > (b); i++)#define forde(i,a,b) for(int i = (a); i >= (b); i++)#define forls(i,n,a,b) for(int i = (a); i != (b); i = n[i])#define mset(a,v) memset(a, v, sizeof(a))#define mcpy(a,b) memcpy(a, b, sizeof(a))#define dout DBG && cerr << __LINE__ << " >>| "#define checkv(x) dout << #x"=" << (x) << " | "<
                  
                   > x#define MIN_LD -2147483648#define MAX_LD 2147483647#define MIN_LLD -9223372036854775808#define MAX_LLD 9223372036854775807#define MAX_INF 18446744073709551615inline int reint() { int d; scanf("%d",&d); return d; }inline long relong() { long l; scanf("%ld",&l); return l; }inline char rechar() { scanf(" "); return getchar(); }inline double redouble() { double d; scanf("%lf", &d); return d; }inline string restring() { string s; cin>>s; return s; }int a[205][205]; ///棋盘const int dx[8]={-1,-2,-2,-1,1,2,2,1}; ///方向增量const int dy[8]={ 2,1,-1,-2,-2,-1,1,2};struct node{ int x, y;};void BFS(int start_x, int start_y, int end_x, int end_y){ queue
                   
                     Q; node N; N.x = start_x; N.y = start_y; Q.push(N); a[start_x][start_y] = 0; while(!Q.empty()) { N = Q.front(); Q.pop(); int x = N.x, y = N.y; if(x == end_x && y == end_y) break; fori(i,0,8) { int nx = x + dx[i]; int ny = y + dy[i]; if(nx >= 1 && nx <= 200 && ny >= 1 && ny <= 200 && a[nx][ny]<0) { a[nx][ny] = a[x][y] + 1; N.x = nx; N.y = ny; Q.push(N); } } }}int main(){ int start_x, start_y, end_x, end_y; while(scanf("%d%d%d%d",&start_x,&start_y,&end_x,&end_y)==4) { mset(a,-1); BFS(start_x,start_y,end_x,end_y); cout << a[end_x][end_y]<