騎士問題
Time Limit:1000MS Memory Limit:65536K
Total Submit:160 Accepted:71
Description
在一個(gè)標(biāo)準(zhǔn)8*8的國(guó)際象棋棋盤上，棋盤中有些格子可能是有障礙物的。已知騎士的初始位置和目標(biāo)位置，你的任務(wù)是計(jì)算出騎士最少需要多少步可以從初始位置到達(dá)目標(biāo)位置。
有障礙物的格子當(dāng)然不可以到達(dá)。
標(biāo)準(zhǔn)的8*8的國(guó)際象棋棋盤中每個(gè)格子可以用唯一的編號(hào)確定。行用1~8這8個(gè)數(shù)字一次表示，列用a~h這8個(gè)字母依次表示如a4,b5等。騎士走日字型。
Input
多組測(cè)試數(shù)據(jù)。
每個(gè)測(cè)試數(shù)據(jù)的第一行是一個(gè)整數(shù)b( -1 <= b <= 62)表示棋盤中有障礙物的格子的數(shù)目，當(dāng)b=-1時(shí)表示輸入結(jié)束。
第二行含b個(gè)不同的有障礙物的格子編號(hào)，用空格隔開，當(dāng)b=0時(shí)，此行為空行。
第三行是騎士的初始格子和目標(biāo)格子的編號(hào)，也用空格隔開。
Output
每組輸出一行格式：
Board n: m moves
其中n表示數(shù)據(jù)的序號(hào)，m表示最少步數(shù)
如果騎士無法到達(dá)，則輸出
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)//統(tǒng)計(jì)步數(shù)
{
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 閱讀(341)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
Questions