#include<stdio.h>
void readdata(); //读入数据
void init(); //初始化
int search(int ); //广度优先搜索
int emptyopen(int); //判栈是否为空:空:1;非空:0。
long takeoutofopen(int); //从栈中取出一个元素,并把该元素从栈中删除
int canmoveto(int,int,int*,int*,int,int); //判能否移动到该方向,并带回坐标(r,c)
int isaim(int row, int col,int d); //判断该点是否是目标
int used(int,int,int); //判断该点是否已经走过
void addtoopen(int,int,int); //把该点加入到open表
int a[10][200][200],n=201; //a存放棋盘,n为迷宫边长
long open[10][2000],head[10],tail[10],openlen=2000; //open表1367
long s[10],t[10],m; //起点和终点
int search(int d)
{
long u;
int row, col, r, c, i, num;
while(!emptyopen(d)) //当栈非空
{
u=takeoutofopen(d); //从栈中取出一个元素,并把该元素从栈中删除
row=u/n; //计算该点所在的行
col=u%n; //计算该点所在的列
num=a[d][row][col]; //取得该点的步数
for(i=0;i<8;i++)
{
if(canmoveto(row,col,&r,&c,i,d)) //判能否移动到该方向,并带回坐标(r,c)
{
if(isaim(r,c,d)) //如果是目标结点
return(num+1); //返回最小步数
if(!used(r,c,d)) //如果(r,c)还未到达过
{
a[d][r][c]=num+1; //记录该点的最小步数
addtoopen(r,c,d); //把该点加入到open表
}
}
}
}
return -1;
}
void main() //为了让search()显示在一页内和main函数换了以下
{ //一般的算法程序main函数写在最上面读起来更方便
int number,i;
readdata(); //读取数据
init();
for(i=0;i<m;i++)//初始化
{
number=search(i); //广搜并返回最小步数
printf("%d\n",number);
} //打印结果
}
int emptyopen(int d)
{
if(head[d]==tail[d])
return(1);
else
return(0);
}
long takeoutofopen(int d)
{
int i;
long u;
if(head[d]==tail[d])
{
printf("errer: stack is empty");
return(-1);
}
i=head[d];
u=open[d][i];
head[d]++;
head[d]=head[d]%openlen;
return(u);
}
int used(int row, int col,int d)
{
if(a[d][row][col]==0)
return(0);
else
return(1);
}
void addtoopen(int row, int col,int d)
{
int u;
if((head[d]-tail[d])%openlen==1)
printf("open table overflow");
u=row;
u=u*n+col;
open[d][tail[d]++]= u;
tail[d]=tail[d]%openlen;
}
void readdata()
{
int i;
long row,col;
scanf("%d",&m);
for(i=0;i<m;i++)
{
scanf("%ld%ld",&row,&col); //起点坐标
s[i]=row*n+col;
scanf("%ld%ld",&row,&col); //终点坐标
t[i]=row*n+col;
}
}
void init()
{
int i;
for(i=0;i<m;i++)
{
head[i]=0;
tail[i]=1;
open[i][0]=s[i];
}
}
int isaim(int row, int col,int d)
{
if(row*n+col==t[d])
return(1);
else
return(0);
}
int canmoveto(int row, int col, int *p, int *q, int direction,int d)
{
int r,c;
r=row;
c=col;
switch(direction)
{
case 0: c--;
r=r-2;
break;
case 1: r--;
c=c-2;
break;
case 2: r++;
c=c-2;
break;
case 3: r=r+2;
c--;
break;//上
case 4: c++;
r=r+2;
break;
case 5: r++;
c=c+2;
break;
case 6: r--;
c=c+2;
break;
case 7: r=r-2;
c++;
break;//上
}
*p=r;
*q=c;
if(r<0||r>=n||c<0||c>=n) //如果越界返回0
return(0);
if(a[d][r][c]==0) //如果是空格返回1
return(1);
return(0); //其余情况返回0
}