UVA 439 骑士(Knight Moves ) 很基础的BFS

Bertha 。 2024-02-17 19:04 145阅读 0赞
  1. #include<cstdio>
  2. #include<queue>
  3. #include<cstring>
  4. using namespace std;
  5. const int maxn=8+2;
  6. struct node{
  7. int x,y;
  8. node(int x=0,int y=0):x(x),y(y){}
  9. };
  10. node ns,nt;
  11. int d[maxn][maxn];
  12. int dir[][2]={
  13. {1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1}};
  14. bool isValid(node & nd){
  15. return nd.x>=1 && nd.x<=8 && nd.y>=1 && nd.y<=8;
  16. }
  17. int bfs(){
  18. memset(d,0,sizeof(d));
  19. queue<node>q;
  20. q.push(ns);
  21. while(!q.empty()){
  22. node u=q.front();
  23. q.pop();
  24. if(u.x==nt.x && u.y==nt.y)return d[u.x][u.y];
  25. for(int i=0;i<8;i++){
  26. node v=node(u.x+dir[i][0],u.y+dir[i][1]);
  27. if(isValid(v) && !d[v.x][v.y]){
  28. q.push(v);
  29. d[v.x][v.y]=d[u.x][u.y]+1;
  30. }
  31. }
  32. }
  33. }
  34. int main(){
  35. char s1[2],s2[2];
  36. while(scanf("%s%s",s1,s2)==2){
  37. ns.x=s1[0]-'a'+1;ns.y=s1[1]-'0';
  38. nt.x=s2[0]-'a'+1;nt.y=s2[1]-'0';
  39. int step=bfs();
  40. printf("To get from %s to %s takes %d knight moves.\n",s1,s2,step);
  41. }
  42. return 0;
  43. }

发表评论

表情:
评论列表 (有 0 条评论,145人围观)

还没有评论,来说两句吧...

相关阅读