http://acm.hdu.edu.cn/showproblem.php?pid=1372
搜索8个可到达的点
View Code
1 #include <stdio.h> 2 #include<string.h> 3 struct node 4 { 5 int tx,ty,num; 6 }q[100001]; 7 int u[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}}; 8 int main() 9 { 10 int i,j,k,n,m,w,x[2],y[2],d,p,f[50][50]; 11 char s1[10],s2[10]; 12 while(scanf("%s %s",s1,s2)!=EOF) 13 { 14 memset(f,0,sizeof(f)); 15 memset(q,0,sizeof(q)); 16 x[0] = s1[1]-48; 17 x[1] = s2[1]-48; 18 y[0] = s1[0]-96; 19 y[1] = s2[0]-96; 20 d = 1; 21 p = 0; 22 f[x[0]][y[0]] = 1; 23 q[d].tx = x[0]; 24 q[d].ty = y[0]; 25 q[d].num = 0; 26 while(p!=d) 27 { 28 p++; 29 if(q[p].tx==x[1]&&q[p].ty == y[1]) 30 break; 31 for(i = 0 ; i < 8 ; i++) 32 { 33 int px = q[p].tx+u[i][0]; 34 int py = q[p].ty+u[i][1]; 35 if(px>0&&px<9&&py>0&&py<9&&!f[px][py]) 36 { 37 f[px][py] = 1; 38 q[++d].num = q[p].num+1; 39 q[d].tx = px; 40 q[d].ty = py; 41 } 42 if(px>0&&px<9&&py>0&&py<9&&!f[px][py]) 43 { 44 f[px][py] = 1; 45 q[++d].num = q[p].num+1; 46 q[d].tx = px; 47 q[d].ty = py; 48 } 49 } 50 } 51 printf("To get from %s to %s takes %d knight moves.\n",s1,s2,q[p].num); 52 } 53 return 0; 54 }