骑士问题
Time Limit:1000MS Memory Limit:65536K
Total Submit:160 Accepted:71
Description
在一个标准8*8的国际象棋棋盘上，棋盘中有些格子可能是有障碍物的。已知骑士的初始位置和目标位置，你的任务是计算出骑士最少需要多少步可以从初始位置到达目标位置。
有障碍物的格子当然不可以到达。
标准的8*8的国际象棋棋盘中每个格子可以用唯一的编号确定。行用1~8这8个数字一次表示，列用a~h这8个字母依次表示如a4,b5等。骑士走日字型。
Input
多组测试数据。
每个测试数据的第一行是一个整数b( -1 <= b <= 62)表示棋盘中有障碍物的格子的数目，当b=-1时表示输入结束。
第二行含b个不同的有障碍物的格子编号，用空格隔开，当b=0时，此行为空行。
第三行是骑士的初始格子和目标格子的编号，也用空格隔开。
Output
每组输出一行格式：
Board n: m moves
其中n表示数据的序号，m表示最少步数
如果骑士无法到达，则输出
Board n: not reachable
Sample Input
10
c1 d1 d5 c2 c3 c4 d2 d3 d4 c5
a1 f1
0
c1 b3
2
b3 c2
a1 b2
-1
Sample Output
Board 1: 7 moves
Board 2: 1 moves
Board 3: not reachable
广度搜索！
代码如下：
#include<stdio.h>
#include<string.h>
int a[8]=
{-2,-2,-1,-1,1,1,2,2};
int b[8]={1,-1,2,-2,2,-2,1,-1};
int p[2][1000];
int s[9][9];
int head;
int tail;
int count;
int x3,y3;
int temp;
#define cr(x) memset(x,0,sizeof(x));
int fun(int x,int y)
{
int x1,y1;
int i;
int x2,y2;
while(head<tail)
{
x1=p[0][head];
y1=p[1][head];
for(i=0;i<8;i++)
{
x2=x1+a[i];
y2=y1+b[i];
if(x2==x3&&y2==y3)
{
return 1;
}
else if(s[x2][y2]==0&&x2>0&&y2>0&&x2<9&&y2<9)
{
p[0][tail]=x2;
p[1][tail]=y2;
tail++;
s[x2][y2]=1;
}
}
if(head==temp)//统计步数
{
temp=tail-1;
count++;
}
head++;
}
return 0;
}
int main()
{
int x,y;
int i,j;
int d;
char c[2];
int x1,y1;
int z=0;
while(scanf("%d",&d)!=EOF&&d!=-1)
{
z++;
for(i=1;i<9;i++)
for(j=1;j<9;j++)
{
s[i][j]=0;
}
for(i=0;i<d;i++)
{
scanf("%s",c);
x=c[1]-48;
y=c[0]-96;
s[x][y]=1;
}
scanf("%s",c);
x1=c[1]-48;
y1=c[0]-96;
scanf("%s",c);
x3=c[1]-48;
y3=c[0]-96;
p[0][0]=x1;
p[1][0]=y1;
s[x1][y1]=1;
count=0;
head=0;
tail=1;
temp=0;
if(fun(x1,y1)==1)
{
printf("Board %d: %d moves\n",z,count+1);
}
else
{
printf("Board %d: not reachable\n",z);
}
}
return 0;
}
posted on 2010-09-19 10:11
jince 阅读(329)
评论(0) 编辑 收藏 引用 所属分类:
Questions