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