时限：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
#include<stdio.h> #define n 200 char a[200][200]={0};//迷宫数组（坐标由0开始） int open[2000],openlen=2000,head,tail; int Berow,Becol;//起点横纵坐标 int Enrow,Encol;//终点横,纵坐标 void init(); int search(); int emptyopen(); int takeoutopen(); int canmoveto(int row,int col,int *p,int *q,int i);//i代表跳马的方向 int isaim(int row,int col); int used(int row,int col); void addtoopen(int row,int col); ///////////////////////////////////////////////////////////////////////// int main() { int m; scanf("%d",&m);//m个测例 for(int i=0;i<m;i++) { init(); int temp=search();//若目标节点不可达，则会返回0 printf("%d\n",temp); } return 0; } void init()//初始化工作 { scanf("%d%d%d%d",&Berow,&Becol,&Enrow,&Encol);//起始点坐标(从1开始的) for(int i=0;i<n;i++) for(int j=0;j<n;j++) a[i][j]=0;//棋盘初始化 head=0; tail=1; open[0]=(Berow-1)*n+Becol-1;//队列初始化 } /////////////////////////////////////////////////////////////////// int search()//寻找最短步长 { int row,col; int u,r,c,num=0; while(!emptyopen()) { u=takeoutopen(); row=u/n; col=u%n; num=a[row][col]; for(int i=0;i<8;i++)//八个方向跳马 { if(canmoveto(row,col,&r,&c,i)) { if(isaim(r,c))//到达终点 return(num+1);//返回最短步长 else if(!used(r,c))//没到达终点且未走到过 { a[r][c]=num+1;//标记走过的点 addtoopen(r,c); } } } } return 0;//全盘搜索后，还是没有找到通路 } int emptyopen()//判断队列是否为空 { if(head==tail) return 1; return 0; } int takeoutopen()//取对列头结点 { int u; u=open[head++]; head=head%openlen; return u; } int canmoveto(int row,int col,int *p,int *q,int i)//i代表跳马的方向 { switch(i) { case 1: row+=2; col--; break;//左下1 case 2: row++; col-=2; break;//左下2 case 3: row--; col-=2; break;//左上1 case 4: row-=2; col--; break;//左上2 case 5: row-=2; col++; break;//右上1 case 6: row--; col+=2; break;//右上2 case 7: row++; col+=2; break;//右下1 case 8: row+=2; col++; break;//右下2 } *p=row; *q=col; if(row>=0 &&col>=0 &&row<n &&col<n &&a[row][col]==0) return 1; return 0; } int isaim(int row,int col)//判断是否到达终点 { if(row==Enrow-1 &&col==Encol-1) return 1; return 0; } int used(int row,int col) { if(a[row][col]==0) return 0; return 1; } void addtoopen(int row,int col)//新结点加入队列 { int u=row*n+col; open[tail++]=u; tail=tail%openlen; }