题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=380

题意容易懂,就是求一个点到另外一个点最少几步(只不过这题的模型是建立在国际象棋棋盘上的),用BFS,此题引入count便于求解(这是关键!)

code:

#include <iostream>
#include <cmalloc>
using namespace std;
typedef struct s
{
int x;
int y;
int count;
}node;
int bfs(int x1,int y1,int x2,int y2)
{
int sum=0,x,y,count1;
if(x1==x2&&y1==y2)
return 0;
node *front,*rear;
rear=front=(node *)malloc(sizeof(node)*10000);

front->x=x1;//入栈
front->y=y1;
front->count=0;
front++;
count1=(rear)->count+1;
while(1)
{

x=rear->x;
y=rear->y;
if( (x-2>=1&&x-2<=8)&&(y+1>=1&&y+1<=8))
{
front->x=x-2;
front->y=y+1;
front->count=count1;
if(front->x==x2&&front->y==y2)
return front->count;
front++;
}
if( (x-2>=1&&x-2<=8)&&(y-1>=1&&y-1<=8))
{
front->x=x-2;
front->y=y-1;
front->count=count1;
if(front->x==x2&&front->y==y2)
return front->count;
front++;
}
if((x-1>=1&&x-1<=8)&&(y+2>=1&&y+2<=8))
{
front->x=x-1;
front->y=y+2;
front->count=count1;
if(front->x==x2&&front->y==y2)
return front->count;
front++;
}
if((x-1>=1&&x-1<=8)&&(y-2>=1&&y-2<=8))
{
front->x=x-1;
front->y=y-2;
front->count=count1;
if(front->x==x2&&front->y==y2)
return front->count;
front++;
}
if((x+1>=1&&x+1<=8)&&(y+2>=1&&y+2<=8))
{
front->x=x+1;
front->y=y+2;
front->count=count1;
if(front->x==x2&&front->y==y2)
return front->count;
front++;
}
if((x+1>=1&&x+1<=8)&&(y-2>=1&&y-2<=8))
{
front->x=x+1;
front->y=y-2;
front->count=count1;
if(front->x==x2&&front->y==y2)
return front->count;
front++;
}
if((x+2>=1&&x+2<=8)&&(y+1>=1&&y+1<=8))
{
front->x=x+2;
front->y=y+1;
front->count=count1;
if(front->x==x2&&front->y==y2)
return front->count;
front++;
}
if((x+2>=1&&x+2<=8)&&(y-1>=1&&y-1<=8))
{
front->x=x+2;
front->y=y-1;
front->count=count1;
if(front->x==x2&&front->y==y2)
return front->count;
front++;
}
rear++;
count1=(rear)->count+1;
}
}
int main()
{
char c1,c2;
int n1,n2,x1,x2,y1,y2,sum;
while(cin>>c1>>n1>>c2>>n2)
{
x1=n1;
y1=c1-‘a’+1;
x2=n2;
y2=c2-‘a’+1;
sum=bfs(x1,y1,x2,y2);
cout<<“To get from “<<c1<<n1<<” to ”
<<c2<<n2<<” takes “<<sum<<” knight
moves.”
<<endl;
}
return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation