首页 > 代码库 > hdu 1372 knight Moves

hdu 1372 knight Moves

Knight Moves

                                                                              Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

                                                                                                   Total Submission(s): 6458    Accepted Submission(s): 3900


题意:在一个8*8的棋盘上给出起始位置和终点用骑士去走其实只能按照国际象棋的规定走要求输出最短路径的大小

简单bfs直接套模板


#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
int ya,yb,vis[10][10];
int ans;
char a[3],b[3];
struct node{

int a,b,depth;//depth记录走的步数
};
int d[8][2]={-2,1, -1,2, 1,2, 2,1, 2,-1, 1,-2, -1,-2, -2,-1};
void bfs(int x,int y)
{
   int i;
   node t,p;
   queue<node> q;
   t.a=x;
   t.b=y;
   t.depth=0;
   vis[t.a][t.b]=1;
   q.push(t);
   while(!q.empty())
   {
       t=q.front();
       q.pop();
       if(t.a==ya&&t.b==yb)
       {
           printf("To get from %s to %s takes %d knight moves.\n",a,b,t.depth);
           return ;
       }
       for(i=0;i<8;i++)
       {
           p.a=t.a+d[i][0];
           p.b=t.b+d[i][1];
           if(p.a>0&&p.a<=8&&p.b>0&&p.b<=8&&!vis[p.a][p.b])
           {
               p.depth=t.depth+1;
               q.push(p);
           }
       }
   }

}
int main()
{


    int xa,xb;
    while(~scanf("%s%s",&a,&b))
     {
         ans=0;
         xa=a[0]-'a'+1;ya=b[0]-'a'+1;
         xb=a[1]-'0';yb=b[1]-'0';
         memset(vis,0,sizeof vis);
         bfs(xa,xb);


     }

    return 0;
}



hdu 1372 knight Moves