UVA 439 骑士（Knight Moves ） 很基础的BFS

Bertha 。 2024-02-17 19:04 142阅读 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 条评论，142人围观）

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

相关阅读