騎士問題
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 閱讀(359)
評論(0) 編輯 收藏 引用 所屬分類:
Questions